B+树相比B树的改进：叶子链表支持顺序扫描

B+树是[[B树索引的节点结构与查询效率]]的一个变种，改动集中在”数据 到底存在哪一层”这一点上：B树的每个关键字（不管在哪一层）都直接 关联对应的数据（或数据指针），而B+树把所有实际数据的关联信息都 下沉到叶子节点——非叶子节点里的每个关键字，只是它右侧指针所指向 子树中最小关键字的”路标”，不再携带指向数据的指针本身。这个改动带来 两个直接好处：第一，非叶子节点因为不需要存储数据指针，能在同样的 节点大小里容纳更多关键字，间接让树更”矮胖”、层数更少；第二，也是 更关键的一点，如果在B+树叶子节点层从最左侧开始给每个节点加一个 指向右侧相邻叶子节点的指针，所有叶子节点就串成了一条按关键字有序 排列的链表——这意味着一旦查询定位到某个起始叶子节点，后续只要顺着 链表指针一路往右扫描，就能按顺序访问到所有满足条件的记录，不需要 反复回到上层节点重新做树形查找。这正是范围查询（如”查询年龄在20到 30之间的所有记录”）和按关键字顺序扫描整张表这两类操作，在B+树上比 在B树上效率明显更高的原因：B树做范围查询依然要在树内反复穿梭定位 每个符合条件的关键字，B+树只需要一次定位加一次线性遍历。