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 .

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

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,

so need to bring up 16 as root and rearrange left and right node . result :

insert 2

find the leaf node (binary search) , put 2 left 6 .which is allowed (2 nodes ≤ max number keys = 2)

insert 1

find the leaf node and put 1 at left side of 2, but again , 3 keys> 2 (max allowed)

so need to bring 2 up to parent node, then check number of keys in parent (2,16) , which is ok , 2 ≤ max allowed keys .

insert 28

find the leaf (17), put new node at right side of 17. check number of keys on current node = 2, still valid , continue

insert 14

find the leaf (6) , put new node (14) at right side of 6, check number of keys in current node = 2, valid, continue

insert 21

find the leaf node (17,28) ,put 21 in the middle . but number of keys in current node become 3,