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 .
- number of keys : the max number of value could be stored on each node
- number of children = number keys + 1
- all leaf nodes must be on same level (perfect balanced)
- on every node, keys are softed linked list
- every node store both key and value
Lets start with a sample . (keys = 2)
it’s an empty tree. insert the root node .
since this is a 2 keys B tree, we directly pack 16 at same node with 17 is stright forward .
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 :
find the leaf node (binary search) , put 2 left 6 .which is allowed (2 nodes ≤ max number keys = 2)
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 .
find the leaf (17), put new node at right side of 17. check number of keys on current node = 2, still valid , continue
find the leaf (6) , put new node (14) at right side of 6, check number of keys in current node = 2, valid, continue
find the leaf node (17,28) ,put 21 in the middle . but number of keys in current node become 3,