第4章：B+ 树、哈希与索引选择

B+ 树结构

B+ 树内部节点保存分隔键和子指针，叶子保存索引项并常按顺序链接。高扇出使树高较小，查询通常读取从根到叶的一条路径。

叶子满时分裂并向父节点插入分隔信息；父节点也可能分裂，直到根。删除要维护占用规则，具体系统也可能采用延迟合并等策略，不能把一种教科书实现当成所有数据库行为。

假设每页可容纳约 200 个子指针，百万级索引项只需少量层级即可定位。根和高层节点常驻缓存后，随机查找的实际 I/O 还会更少。

B+ 树支持有序范围扫描：先找到下界，再沿叶子遍历。哈希索引适合等值定位，但通常不能凭散列值高效回答原键顺序区间。

索引 (cid,score) 按 cid、再按 score 的字典序组织。条件 cid=7 AND score>=90 可形成连续区间；只有 score>=90 通常不能得到一个同样简单的连续区间。

覆盖索引包含查询所需字段时，可能减少回表。但索引维护增加写入、空间和缓存成本，不能给每列任意叠加索引后只期待收益。

聚簇组织使数据记录与某个键的顺序接近，有利于范围扫描。非聚簇索引可能产生许多分散的记录访问。若范围很大，按索引逐条回表可能比顺序扫表更贵。

例如查询命中一半记录，若记录几乎均匀分散在所有数据页中，即使索引能列出一半键，也可能最终读取几乎全部数据页，并额外支付索引访问成本。

Bloom filter 用位数组和多个哈希函数判断元素可能存在。标准构造允许假阳性，不允许对已正确插入且未被错误删除的元素给出假阴性。

它可以在查磁盘结构前排除不可能命中的情况，但“可能存在”仍需真正查询。它既不是精确索引，也不负责返回记录位置。