0
$\begingroup$

I have a b+ tree and i want to find the record associated with a specific key Ki. So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists in the table and we can return the record associated with Ki.

Since the leaf nodes have the same structure of internal nodes, how can the algorithm know if a node is a leaf node ?

$\endgroup$
0
$\begingroup$

There are two common ways that the implementation of any B-tree variant decides if you're at a leaf node or not.

  1. Most B-tree implementations include a tiny header in each node (e.g. to store the number of elements/pointers in the node). It might only be a word in size, but even then, it's usually not hard to find one spare bit to mark leaf nodes vs internal nodes.
  2. Unless you are in the middle of a difficult rebalance operation, all leaf nodes are at a fixed depth in any B-tree. So knowing this fixed depth means you can just keep track of how "deep" you are in the tree while searching and you will know when you reach a leaf.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.