Search code examples
databaseindexingtreenodesb-tree

Why are there two leaf nodes in this B-Tree lookup?

In this

enter image description here

graphic, we are looking up employee_id 123 and subsidary_id 20 in a B-Tree (from a tutorial on database indexes). There are two leaf nodes branching off the tree. Is this purely demonstration, or is there something I'm missing, as I would think that the only leaf node that would need to be checked would be the top one, as it has employee_id max 123 and subsidary_id max 27.

Solution

  • The diagram itself isn't showing the actions of that particular search, rather it's showing a localised portion of the tree, so I wouldn't read too much into it for the specific query.

    You're absolutely correct in that searching for the key 123-20, you never need to follow the link to the second leaf node (either through the hierarchical link from the left, or the sequential link from above).

    However (and this is hard to tell without seeing the source material), it's quite likely that this diagram may be used for something else as well.

    The fact that it shows links between consecutive leaf nodes means that it would be quite easy to use the index lookup to locate a specific entry, then sequentially process them.

    By that I mean a query like "give me every record with an employee ID of 123", or "give me all records with an employee ID between 123 and 456", or "give me all records in employeeID/subsidiaryID order".

    All those queries would entail finding a specific record using the hierarchical path (though the final one may have a quicker path direct to the first record), then following the sequential path for subsequent records.

    In addition, the fact that the subsidiary IDs of 20 are both red means that it would be an ideal opportunity to educate the reader on the fact that the employee-subsidiary index is not necessarily the best one for all queries. In other words, an efficient query "give me all records from subsidiary 20" would be better with another index (one containing simply the subsidiary ID).

    That'd be my best guess, it would be worthwhile looking at the tutorial to see if that diagram is used for something else.

    Of course, it could be that the person putting together the tutorial couldn't be bothered creating a new graphic so simply used one from a different question, or an earlier iteration of the tutorial :-) I've been guilty of that before.