不用翻遍整张表，数据库怎样找到一行？

• 上下界相同时是等值查询，例如 63…63；输入 38…47 则包含两端的范围。控件接受 0 到 99 的整数，拒绝非法或颠倒的边界。
• 切换全表扫描和 B+ 树查找，数据、条件与记录内容保持一致。通过步骤滑块、方向键或上一步、下一步检查真实访问轨迹。
• 查询 42。默认排列 A 中，三个同键项分别是 r6、r7、r8，都必须保留。键值不是记录身份。
• 插入一个键。即使键已存在，也会分配新的行号与堆位置。查看最近一次插入的局部步骤，再回到已经提交的整树上查询。最多新增 30 行。
• 切换堆顺序会用相同的原始键值多重集重新建表，行号按新插入顺序分配。两种访问方案始终在同一份选定的表上比较。
• 重置恢复排列 A、查询边界 63…63、索引路线、插入键 79、零新增行、查询与分裂的第一步，并关闭规则说明。

在一本没有目录的记录本里找东西，可能要一页页翻。另备一份排好顺序的目录，就能先查目录，再找到记录所在的页。数据库索引也做类似的事：它保存查找线索，原来的完整记录还在原处。

表里的记录，不一定按查询的键值存放。本例有 24 条完整记录，分在 6 张堆页中；每页最多 4 行，顺序由固定种子打乱后的插入顺序决定。查询条件是键值 63。全表扫描逐行检查，找到目标以后也继续，因为后面可能还有同键记录。

B+ 树另外保存一份有序的键值与行号对。内部页装分隔键与子页指针，叶页装索引项，并连接下一张叶页。索引项指向堆里的完整记录。因此，这是一个微型的非覆盖二级索引，并没有把原表按键值重新排好。PostgreSQL 文档说明了普通索引查询为何往往还要访问表。

在默认数据中，键值 63 对应行号 r14，完整内容为 item-14，位于堆页 H4。两种访问路线取回的是同一行。

这些是模型计算的访问计数，不是毫秒、磁盘读取次数或加速倍数。每次查询从空缓存开始，访问过的页全部保留；同一页重复触及时，在「不同页」里只计一次。比较次数统计三路比较器的调用，不统计处理器指令。把两段轨迹放在相同的影片进度上，也不代表它们执行了相同时间。

本例约定：先按整数键值升序，再按唯一行号升序。不支持字符串排序、空值或浮点键。独立模型接受 −1,000,000 到 1,000,000 的整数；控件有意只开放 0…99。

每个内部分隔键，准确等于右侧子树最小的「键值、行号」对。查询对小于分隔键时留在左侧，等于或大于时走右侧。查找下界时，使用 (下界, 0)；真实行号从一开始，因此这个查询对排在所有同键记录之前。

这可能让查询先落在前一张叶页，然后沿下一叶页指针继续检查，直到键值超过上界。这是刻意简单且正确的下界策略，并非 PostgreSQL 的优化实现。CMU 的 B+ 树讲义介绍了用行号区分重复键的方法。

教学叶页最多装三项。第四项产生暂时溢出，随后分成两张各有两项的叶页，修好邻居链接。把右页最小的一项复制到父页，配上新子页指针；右叶页里仍保留这一项。

内部页最多连接四个子页。第五个指针产生溢出时，本实现把三个子页留在左侧、两个放到右侧。两边之间的分隔键上推到父页，不再保留在分裂后的两个内部页中。如果旧根也分裂，就创建一个新根连接两边，让全部叶子统一加深一层。PostgreSQL 的 B-tree 实现文档也说明了分裂向父页传播与根增长的过程。

影片插入序列固定为 40, 53, 66, 79, 92, 5, 18, 31, 44, 57, 70, 83, 96。键 79 用来观察叶页分裂；键 96 触发叶页分裂、两次内部页分裂，最后创建新根。提交后的树从三层长到四层。分裂停帧明确标注为局部快照：新页此时可能还没有接入父页。查询只在完成提交的树上执行。

新增十三行以后，共有三十七行，存放在十张堆页中。请求全部 0…99 的键时，索引路线触及十七张索引页，还要访问全部十张堆页，总计二十七张不同页。全扫只触及十张堆页。两者的比较器调用分别为七十七次和七十四次，最终行号与内容逐一相同。

选择性强的查询可以减少表访问，但索引也占空间，写入时也要维护。实际选择还取决于缓存、页大小、局部性、查询范围、并发与执行计划；覆盖索引和仅索引扫描也有不同前提。本场景没有模拟这些优化，也没有删除、合并、事务、MVCC、锁、持久化、真实存储设备或生产耗时。