Overview
- Definition: A balanced tree data structure designed for efficient disk-based storage and retrieval
- Purpose: Optimizes database indexing by minimizing disk I/O operations
- Key characteristic: Self-balancing to maintain fast traversal even with data changes
Structure
- B-Tree consists of nodes organized in a hierarchical structure
- In a B-Tree of order ‘m’ (or degree ‘m’): - Each node can have up to ‘m’ child nodes - Each node contains up to (m-1) elements/keys - All leaf nodes appear at the same level (balanced)
Node Types
- Root Node: The topmost node in the tree
- Internal Nodes: Nodes that have children
- Leaf Nodes: Nodes at the bottom level with no children
- Each node typically corresponds to one disk page in storage
Data Organization
- Each element in a node has: - A key (used for searching/sorting) - A value (usually a data pointer to the actual record)
- Data pointers can reference: - The actual data tuple/row (PostgreSQL approach) - The primary key (MySQL approach) - Note: Uber migrated from PostgreSQL to MySQL, changing this pointer strategy
Properties
- All keys within a node are kept in sorted order
- For any node with keys k₁, k₂, …, kₙ: - All keys in subtree of child 0 are < k₁ - All keys in subtree of child i are between kᵢ and kᵢ₊₁ - All keys in subtree of child n are > kₙ
- The tree grows and shrinks from the root, maintaining balance
Limitations
- Elements in all nodes store both the key and the value
- Internal nodes store data pointers, taking more space and requiring more I/O operations
- Range queries are inefficient due to random access patterns (e.g., retrieving all values between 1-5)
- B+ Trees were developed to address these limitations