Search code examples
data-structuresb-tree

Why B+ tree need to have pointer pointing to next block?


At the leaf node of a B+ tree, there are two pointers, one is pointing to the data block, another is pointing to next index block.

However, I'm not quite sure about the usage of the index block pointer in a B+ tree. When we perform searching, we follows a sets of "is A greater than B" checking, eventually it would always bring us to the index block which contains the data. So, why we still need the index pointer in order to jump to next index block?


Solution

  • To support faster sequential traversal (constant O(1)). You may avoid this pointer if all you need are random read requests. You may as well add a pointer to the previous block when a fast inverse sequential traversal is needed.