B Tree And B+ Tree

Both BTree and B+Tree are self-balancing tree:

B Tree

In here with the magnitude of 3 we can have 3-1 = 2 nodes on the same rows and 3 different branches

Problem: The cost here is searching. Say if you want to search for 1 and then 3 and then 5 you need to go through root 0002 0004 every single time

B+ Tree

B+ Tree solves the above problem by maintaining a linked list and duplication of a node at the leave level

For example in here to search for something, you can just directly jump to that node and search in the leave level.

In here we satisfy the cost of building, however the cost of building B tree is much less comparing to B+ tree

Use case:

• B Tree: suitable in less memory system because values are stored in the same node
• B+ Tree: suitable in higher read I/O system since the structure is easier to navigate