Q:

Larger than memory data structures and how they are typically handled

Say I have a file based data structure such as a B+ Tree.  My understanding is that the data is expected to be stored on disk, but the index is usually loaded in memory.  What if you have such a large file that even its index doesn't fit into memory?  How is that typically handled? Secondly, since the index is a tree, not a linear set of data, how is it usually laid out on disk?
I'm basically curious about how it is done in real-world projects (such as Berkeley DB).  Obviously I'm interested in broad strokes.  I'm hoping to get an idea so I have some context when I dig into the B-Tree section of my database book (or jog my memory from CS XYZ from years ago)

A:

B-trees are intended for page-based systems, where a given node fits into a page. To find an entry in a B-tree, it is only necessary to load in one page at a time, so you can do that.
Even updating them doesn't require a large number of pages being in memory at the same time - I imagine the most difficult operation is a delete when nodes are being reorganised, but if it's implemented carefully even that could be done with relatively few pages in memory.

