49:54
#31 B+Trees on Disks | Introduction to Database Systems
NPTEL-NOC IITM
Overview
This video introduces B+-trees as an efficient data structure for managing dynamic files in database systems, particularly for disk-based storage. Unlike in-memory trees, B+-trees are designed to optimize disk I/O by treating disk blocks as nodes. This leads to a high fan-out, significantly reducing the tree's height and thus the number of disk accesses required for searches. The lecture details the structure of B+-trees, differentiating between internal nodes (which guide searches) and leaf nodes (which store record pointers). It explains how insertions and deletions are handled, including node splitting and merging to maintain balance and efficiency. Finally, it highlights the advantages of B+-trees, such as fast random access and sequential traversal of records, while also noting the potential bottleneck at the root node.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- Previous index structures (primary, clustering, secondary) are costly to modify in dynamic files.
- Hashing can manage dynamic files, but B+-trees offer an alternative.
- B+-trees are tree-based structures optimized for disk access.
- Disk access is block-based (e.g., 4KB), so nodes are designed to be disk blocks.
- High fan-out (many children per node) reduces tree height.
- B+-trees are balanced, self-balancing trees.
- All leaf nodes are at the same level.
- Internal nodes contain index information (keys and pointers) to guide searches.
- Leaf nodes contain key-value pairs and pointers to actual data records.
- Leaf nodes are linked together sequentially to allow ordered traversal.
- An internal node of order 'm' has at most 'm' tree pointers and 'm-1' keys.
- Keys are sorted and guide the search to the appropriate child pointer.
- Pointers (P1, P2, ...) point to sub-trees.
- Internal nodes do not directly point to data records.
- Nodes are at least half-full (except possibly the root) to ensure balance.
- Leaf nodes store pairs of (key, record pointer).
- Leaf nodes have a pointer to the next leaf node, forming a linked list.
- A leaf node of order 'm_leaf' holds at most 'm_leaf' record pointers and keys.
- Leaf nodes are also at least half-full.
- The structure of leaf nodes differs from internal nodes.
- The order 'm' is determined by block size (B), key size (V), and pointer size (P/Pr).
- Inequalities are used: m*P + (m-1)*V <= B for internal nodes, and m_leaf*Pr + m_leaf*V + P <= B for leaf nodes.
- These calculations ensure nodes are filled efficiently based on disk block size.
- Typical values lead to high fan-out (e.g., 30-40 children per node).
- The height of B+-trees is usually very small (e.g., 3-4 levels).
- Illustrative example with small 'm' and 'm_leaf' values (m=3, m_leaf=2).
- Keys in internal nodes guide the search down the tree.
- Search terminates at a leaf node, retrieving the record pointer.
- Leaf nodes are linked, allowing sequential traversal of records in sorted order.
- Insertion starts by searching for the correct leaf node.
- If the leaf has space, the new key-record pointer pair is added.
- If the leaf overflows, it splits into two nodes.
- The middle key is promoted to the parent internal node.
- If an internal node overflows, it also splits, and its middle key is promoted, potentially increasing tree height.
- Deletion involves finding the key in a leaf node and removing it.
- If a leaf node underflows (becomes less than half full), it may borrow from a sibling.
- If borrowing is not possible, nodes merge.
- Deletion in internal nodes requires updating parent pointers and potentially merging or borrowing.
- Deletions can cause the tree height to decrease (level drop).
- Provides efficient random access (logarithmic in height, few block accesses).
- Supports efficient sequential access via linked leaf nodes.
- Handles dynamic data efficiently through splitting and merging.
- The root node can become a hotspot due to frequent access for all searches.
- Concurrency control can be challenging at the root.
Key takeaways
- B+-trees are optimized for disk-based databases by using disk blocks as nodes, leading to a high fan-out and shallow tree structure.
- Internal nodes guide searches using keys and pointers, while leaf nodes store actual record pointers and are linked for sequential access.
- The structure is self-balancing, maintaining efficiency through node splitting during insertions and merging/borrowing during deletions.
- The order 'm' of a B+-tree node is determined by disk block size and data element sizes, maximizing the number of entries per block.
- B+-trees offer both fast random access to records and efficient ordered traversal of the entire dataset.
- Insertions and deletions dynamically adjust the tree, potentially increasing or decreasing its height.
- A key challenge with B+-trees is the potential for the root node to become a performance bottleneck (hotspot) due to high contention.