B.rar_B树_B树 java_b 树 索引_树 搜索

B-Trees

Dictionaries for very large files typically reside on secondary storage, such as a disk. The

dictionary is implemented as an index to the actual file and contains the key and record

address of data. To implement a dictionary we could use red-black trees, replacing pointers

with offsets from the beginning of the index file, and use random access to reference nodes

of the tree. However, every transition on a link would imply a disk access, and would be

prohibitively expensive. Recall that low-level disk I/O accesses disk by sectors (typically 256

bytes). We could equate node size to sector size, and group several keys together in each

node to minimize the number of I/O operations. This is the principle behind B-trees. Good

example, all keys less than 22 are to the left and all keys greater than 22 are to the right. For

simplicity, I have not shown the record address associated with each key.

Figure 4-3: B-Tree

We can locate any key in this 2-level tree with three disk accesses. If we were to group 100

keys/node, we could search over 1,000,000 keys in only three reads. To ensure this property

holds, we must maintain a balanced tree during insertion and deletion. During insertion, we

examine the child node to verify that it is able to hold an additional node. If not, then a new

sibling node is added to the tree, and the child’s keys are redistributed to make room for the

new node. When descending for insertion and the root is full, then the root is spilled to new

children, and the level of the tree increases. A similar action is taken on deletion, where child