Those Data structures can not be learned from leetcode- B Tree B+ Tree

A step by step introduction to B tree (and B+ tree) with details samples.

We may not have to implement a B(+) Tree, but it still good to understand how it works as a senior(lead) developer; because this will help us in making important design choices in order to get a optimal solution , and how bad the performance could be w/o index; and answer the question “Do you know B Tree?” during your FANG interview ;and also, to have fun .

Lets start .

B Tree

Rule

1. number of keys : the max number of value could be stored on each node
2. number of children = number keys + 1
3. all leaf nodes must be on same level (perfect balanced)
4. on every node, keys are softed linked list
5. every node store both key and value

Lets start with a sample . (keys = 2)

Insert process

insert 17

it’s an empty tree. insert the root node .

insert 16

since this is a 2 keys B tree, we directly pack 16 at same node with 17 is stright forward .

insert 6

Trying to put 6 left 16, but can not, only have 2 keys allowed in every node,