> If you had an oracle that could tell you how to get to the book you need, the navigation instructions to get to the book will be at least as long as the book, on average.

Only if the oracle has all books that could possibly exist. If you're trying to find a book that already exists, that set is infinitely smaller.

The oracle doesn't have the books. The library does. And it has all of them. Directions to each book depend only on the layout and contents of the library.