15.4. 基于树的索引¶
15.4.1. 基于树的索引¶
线性索引在数据库静止时是高效的，也就是说，记录很少甚至从不插入和删除。 ISAM 能应付有限次数的更新，但应付不了频繁的变化。由于本质上只有两级索引，对于真正大型的数据库——柱面数量大到顶层索引无法装入内存——ISAM 同样会失效。
在最一般的形式下，数据库应用具有以下特征：
大量记录且更新频繁。
查找基于一个键或多个键的组合。
使用键范围查询或最小/最大查询。
对这类数据库，必须找到更好的组织方式。一种做法是用二叉搜索树（BST）来存储主键和次键索引。 BST 可以存储重复的键值，提供高效的插入、删除和查找，还能执行高效的范围查询。当内存足够时，BST 是实现主键索引和次键索引的可行选择。
遗憾的是，BST 可能失衡。即使在相对良好的条件下，叶结点的深度也很容易相差一倍。当树存储在内存中时，这可能不是大问题，因为查找和更新的时间仍是 \(\Theta(\log n)\)。但当树存储在磁盘上时，结点在树中的深度就变得至关重要。每次访问 BST 结点 \(B\)，都必须访问从根到 \(B\) 路径上的所有结点。这条路径上的每个结点都要从磁盘取出。每次磁盘访问返回一个信息块。如果某结点与其父结点在同一块上，那么一旦父结点已在内存中，找到该结点的成本就微不足道。因此，最好把子树放在同一块上。遗憾的是，很多时候结点并不与父结点同块。于是，对 BST 结点的每次访问都可能需要再从磁盘读一个块。如果 BST 访问表现出良好的引用局部性，用缓冲池在内存中保存多个块可以缓解磁盘访问问题。但缓冲池无法完全消除磁盘 I/O。 BST 失衡时问题更严重，因为深层的结点可能导致读取许多磁盘块。因此，要让基于磁盘的 BST 具有高效查找，必须解决两个关键问题。第一是如何保持树的平衡。第二是如何把结点安排到磁盘块上，使从根到叶的任何路径上遇到的块数最少。
我们可以选择一种平衡 BST 和向磁盘块分配结点的方案，使磁盘 I/O 最小化，如第一张幻灯片所示。然而，在插入和删除面前维持这种方案很困难。特别是，更新发生时树应当保持平衡，但这可能需要大量的重组。每次更新应该只影响少数几个块，否则代价太高。
从这张幻灯片可以看到，采用"BST 必须是完全树"之类的规则会导致树内数据的大量重排。
我们可以改用另一种树结构来解决这些问题：它能在更新后自动保持 平衡，并且便于分块存储。 平衡树数据结构有很多种， 也有一系列保持 BST 平衡的技术。 例子包括 AVL 树和伸展树。 作为替代， 2-3 树（2-3 tree） 具有所有叶结点都在 同一层的性质。 这里优先讨论 2-3 树而不是其他平衡搜索树的主要原因是： 它自然地引出 B 树（B-tree）——迄今使用最广泛 的索引方法。
