CODEWITHSUNDEEP
data-structuresb-tree
Shiu Chun Ming
Shiu Chun Ming

Reputation: 227

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?

Upvotes: 2

Views: 1229

Answers (2)

Alper Fırat Kaya
Alper Fırat Kaya

Reputation: 2359

A B+ tree is a data structure often used in the implementation of database indexes. Each node of the tree contains an ordered list of keys and pointers to lower level nodes in the tree. These pointers can be thought of as being between each of the keys. To search for or insert an element into the tree, one loads up the root node, finds the adjacent keys that the searched-for value is between, and follows the corresponding pointer to the next node in the tree. Recursing eventually leads to the desired value or the conclusion that the value is not present.

Now think this scenario you need to search something from b+ tree but all of them is in the disk remember disk access is very slow and Reading a single block takes just as much time as reading a partial block. You can not fit the b+ tree to ram. You took the some part of the tree to the ram and searched it. And couldn't find the value what you are looking for. Isn't it nice to have a pointer to next block to lower the disk access ?

Upvotes: 0

Lior Kogan
Lior Kogan

Reputation: 20608

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.

Upvotes: 1

Related Questions