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,

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,