supported operations
- insert(key, object)
- lookup(key)
- delete(key)
- each node will store (key, object), but we will ignore the “object” part and only consider the “key” part…
B-tree
B stands for Boeing or balance?
B-tree is a BST where for a certain $t \geq 2$:
- each node (except the root) has between $t-1$ to $2t - 1$ keys
- keys are stored in a sorted array
- the root has between 1 to 2t - 1 keys
- each non-leaf node has degree (number of children) equals to number of keys it stores + 1
- enforce that the i-th child has keys that are between the (i - 1)-th and i-th keys of its parent…
- all leaf nodes are at the same depth (i.e. perfectly balanced!)
operations
- insert (key, value):
- walk down the tree
- split whenever encounter a full node (a node with degree 2t)
- insert the (key, value) when arrive at the leaf node
- split: to split a node, pull the median key to the parent, split the remaining keys into 2 nodes of t - 1 keys, then connect these 2 nodes to the parent
- if the node being split is the root, create a fresh new node with 1 key!
- remove: more complicated….