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$

2 Answers 2

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$
0
$\begingroup$

This is code dependant issue, ie it depends on the way u wrote the code & defined the data structure in it.

If u r following the Wikipedia code ( took it from there). I didn't read the whole code but according to the fig they're attachingenter image description here

-A leaf node has children links = Null (or nil depending on the programming language u r using) -Also, the internal nodes linked list link ( the red square in the Fig) should equal Null as opposed to leaf nodes. -Since this is only 1 pointer, ie easier to check, u could write something like

While (node.linked_list != Null)

To stop the loop when u reach a leaf

(Note that a storage saving code would use one of the children links, say the 1st, as the linked list link, substituting the need to another pointer field by 1-bit Boolean flag identifying leaf nodes and consequently the meaning of this pointer)

Ps.

That's a 2 yrs old question, probably the student graduated & already became a developer by now!!!!

$\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.