A way of storing data on disk in a balanced tree format.

Basically at the bottom of the tree you have data blocks, then you have internal nodes pointing to the datablocks with keys. With the internal nodes you try and pack as many pointers as you can into the node, giving you a huge branching factor. As an internal becomes full, you split it into two, and add pointers to those two new internal blocks into the parent node. If you are the root of the tree, you create a new parent node. This is how the tree remains balanced, since new internal nodes are added at the root instead of at the leaves. It's very fast and efficient because you can cache the internal nodes in the tree and save a lot of time searching for data.


lib/main.php:839: Notice: PageInfo: Unknown action