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