Larger than memory data structures and how they are typically handled

Question

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)

Answer 1

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.

Answer 2

You might want to take a look at SQLite. The code base is much smaller than Berkeley DB, it's public domain, it's very clearly organized and commented, and the out-of-source documentation is excellent. Taught me a lot about btrees in the real world

Answer 3

To answer your first question, a data structure that is too large to fit into memory is usually divided into "pages", usually all pages are the same size and each page contains part of the data structure, to use the data you load and unload pages.

Another common option (that is not commonly used in RDBMS but is common with things like XML and media files) is streaming, where you process the data in order by loading the next section and discarding the previous one.

And that also answers your second question, if you use paging than the file structure is a sequence of pages of the same size, if you use streaming than the data should be laid out in the order you're going to use it (in the case of a tree it's likely going to be either DFS or BFS order, depending on your application).