Binary Search Tree (BST)
- Not appropriate for a disk-based data structure due to
- The cost of tree balancing
- Low fanout (the maximum number of child nodes)
- Locality
- A node is not stored in key order
- Child pointers can point to several disk pages
- which leads to a high cost of disk search
Disk-based Data Structure
- Block
- The smallest unit of operation
- Should read the whole block to read part of the block
- Ideal data structure
- High fanout and low height
- Low number of node pointers and low frequency of balancing
- Consider the internal structure of the storage device (HDD/SSD)
B-tree (B+ tree)
- Each node
- stores N keys and N+1 child pointers
- is considered as a page on disk
- Search Algorithm
- Binary search from the root node to the target leaf node
- Binary search within the node as well
- Rebalancing
- Overflow
- Splits a node
- Occurs once a key is inserted
- Underflow
- Merges nodes into one node
- Occurs once a key is deleted
