数据结构: B+树

Posted on Edited on In , Word count in article: 3.7k Reading time ≈ 14 mins.

B+树

概述

  • B+树 是一种多路平衡搜索树，主要面向磁盘、固态硬盘等外部存储场景
  • 与普通二叉搜索树每个结点只保存一个键不同，B+树 的一个结点可以保存很多个键和子指针，因此树的分支数很大
  • B+树 将索引导航信息放在内部结点，将记录指针或记录本身统一放在叶子结点，并把所有叶子结点连接成有序链表
  • 数据库索引使用 B+树 的核心原因，是在较少的页访问次数下完成有序查找和范围扫描

基本结构

结点组成

  • B+树 是一棵多路搜索树，常用 m 阶表示内部结点最多拥有 m 个子指针和 m-1 个分隔键，不同教材对阶的定义可能略有差异

    • 根结点可以是叶子结点，也可以拥有较少的子结点
    • 非根内部结点通常至少半满，以避免树的空间利用率过低，具体下限由实现的页布局决定
    • 内部结点中的键用于划分子树的取值范围，键本身通常只是导航信息，不保存对应记录的完整内容

  • 叶子结点保存有序的键，以及与键对应的记录指针、主键值或记录内容

    • 在聚簇索引中，叶子结点可能直接保存整行记录
    • 在二级索引中，叶子结点通常保存索引键和主键值，再通过主键定位整行记录

  • 所有叶子结点位于同一层，因此从根到任意叶子的路径长度相同

  • 内部结点中的分隔键可能在叶子结点中再次出现，这种重复是为了让内部结点承担路由职责

  • 下面的示意图中，20 和 40 只是根结点的分隔键，真正的记录都在叶子结点中

    1
    2
    3
    4
    5
                      [20 | 40]
                   +-------+-------+
                   |       |       |
    [5, 10, 15] <-> [20, 25, 35] <-> [40, 50, 60]
       records          records           records
    • 小于 20 的键进入最左子树，大于等于 20 且小于 40 的键进入中间子树，大于等于 40 的键进入最右子树
    • 叶子之间的双向连接不是树的父子关系，而是为了支持按键的顺序向后扫描

查找路径

  • 查找一个键时，从根结点开始比较分隔键，选择可能包含目标键的子指针，重复这个过程直到叶子结点
  • 内部结点只承担导航职责，使单个内部页可以容纳更多分隔键和子页指针
  • 到达叶子结点后，在叶子页内查找目标键，再根据记录指针或主键值访问记录
  • B+树 的高度通常接近 log_m n，其中 m 是较大的扇出，n 是索引项数量

数据结构特性

  • 高扇出：一个结点可以连接很多子树，树的高度远小于同样数据量的二叉树
  • 平衡：所有叶子处于同一层，不会像未平衡的二叉搜索树一样因为插入顺序退化成链表
  • 有序：叶子中的键按照索引键排序，父结点的分隔键也按照从小到大的顺序排列
  • 适合范围访问：定位到范围起点后，可以沿叶子链表依次访问后续叶子，不需要反复从根结点开始查找
  • 适合页式存储：一个内部结点通常可以设计成一个或几个存储页，访问结点时可以批量读取多个键和指针
  • 查询成本可以拆成两部分：先沿树高定位起点，再沿叶子链表读取结果，点查询接近 O(log_m n)，返回 k 条连续结果的范围查询接近 O(log_m n + k)

为什么索引通常使用 B+树

磁盘页访问比比较次数更重要

  • 数据库索引通常持久化在存储设备上，执行查询时真正昂贵的部分往往是随机页访问，而不是在一个页内比较几个整数
  • B+树 通过较大的扇出降低树高，点查询通常只需要访问根页、若干内部页和一个叶子页
  • 内部结点不保存完整记录，单页可以放下更多分隔键和子指针，因此在相同数据量下往往比保存记录指针的树更矮
  • 根页和上层内部页还容易被缓存在内存中，后续查询可能只需要访问较少的叶子页

有序结构适合范围查询

  • >、<、BETWEEN 等范围条件可以先在树中定位第一个叶子位置，再沿叶子链表顺序读取后续键
  • ORDER BY、按时间区间读取、前缀匹配等需求都能利用索引键的全局有序性
  • 如果记录按键在叶子中连续排列，范围扫描可以沿兄弟指针顺序访问，并有机会被存储引擎预取，这比在大量分散结点之间跳转更适合存储设备

结构规则稳定

  • B+树 始终保持平衡，索引规模增长时树高只会缓慢增加，查询延迟更容易预测
  • 结点的分裂、合并和页回收会维护每个结点的容量约束，因此不会因为数据输入顺序而出现普通二叉搜索树的极端退化
  • 这并不表示所有数据库索引都必须使用 B+树，只是它同时满足低树高、有序访问和范围扫描，覆盖了关系型数据库最常见的索引需求

为什么不使用 B树

  • B树 和 B+树 都是多路平衡搜索树，主要差异在于 B树 可以在内部结点和叶子结点保存记录，而 B+树 将记录统一放到叶子结点
  • B树 的点查询有机会在内部结点提前命中记录，这是它的一个局部优势，但数据库查询的主要成本通常是页访问
  • B树 的内部结点带有更多记录信息，单个页能容纳的路由键和子指针更少，扇出可能降低，树高和页访问次数可能增加
  • B树 没有要求所有叶子通过一条统一的有序链表连接，范围查询需要在树的多个层级之间进行中序遍历，访问模式不如 B+树 直接
  • B+树 可能重复保存分隔键，换取内部结点更轻、叶子范围扫描更简单，这种空间上的重复通常值得
  • B树 并不是错误的选择，在数据完全位于内存、点查询占绝大多数且记录较小时，它仍然可以有合适的实现，只是通常不是关系型数据库磁盘索引的优先方案

为什么不使用红黑树

  • 红黑树是二叉平衡搜索树，每个结点通常只有一个键和少量指针，B+树 则把大量键和指针放进一个面向页的结点
  • 两者在内存模型下都可以达到 O(log n) 的查找复杂度，但这个记号没有体现存储设备上的页访问次数
  • 红黑树沿查找路径一次跳转一个结点，结点可能分散在内存或磁盘中，容易产生大量指针跳转和缓存未命中
  • B+树 每次读取一个内部页就能获得大量比较对象，并且相邻叶子可以沿兄弟指针访问并有机会预取，更适合批量读取，物理页是否连续则取决于存储布局
  • 红黑树的中序遍历也能完成范围查询，但结果结点之间通常通过树指针连接，不能天然转化为叶子页的顺序扫描
  • 红黑树更适合进程内的有序映射、集合等数据结构，数据库磁盘索引更关心页布局和范围访问，因此通常选择 B+树

B+树的缺点

  • 维护成本：索引规模变化时可能发生页分裂、页合并和父结点更新，这些结构调整会带来额外的写入和日志开销
  • 空间成本：分隔键可能在内部结点和叶子结点中重复出现，叶子链表还需要额外的兄弟指针
  • 宽键问题：联合索引包含的列越多、键值越长，单页能容纳的索引项越少，扇出下降后树高和存储空间可能增加
  • 低选择性问题：如果范围覆盖了大部分叶子，扫描索引后再回表可能比直接扫描数据表更慢，优化器可能放弃使用索引
  • 不适合所有查询：纯等值查询在具体引擎支持哈希索引时可能更适合哈希结构，而 B+树 的主要优势是有序性和范围访问

最左前缀原则

联合索引的排序方式

  • 假设联合索引的列顺序为 (a, b, c)，叶子中的索引键按照字典序比较，先比较 a，a 相同时再比较 b，前两列都相同时才比较 c 
    1
    (1, 1, 1) -> (1, 1, 2) -> (1, 2, 1) -> (1, 3, 1) -> (2, 1, 1)
  • 可以把联合索引理解为两个方向同时发生
    • 创建索引时，列顺序从左到右固定为 a、b、c，组合键的比较也从左到右进行
    • 查找时，B+树从根页向下导航，先依据 a 划分较大的子树范围，再在确定的 a 范围内依据 b 细分，最后依据 c 定位
    • 这里的“从树顶向下”描述的是搜索过程，不是说树的每一层只存一列，实际内部结点保存的通常仍是完整的联合键
    • 只有前面的列已经相等或确定边界，后面的列才有机会继续参与比较和计算
  • 联合索引不是先为 a、再为 b、再为 c 各建一棵独立的树，而是把它们组合成一个有序键，在自上而下的搜索中逐步确定范围
  • 固定 a=1 可以得到一段连续的叶子区间，固定 a=1,b=2 可以在这段区间中继续得到更小的连续区间
  • 如果只给出 b=2，满足条件的键会分散在 a 的每个取值区间中，根结点无法仅凭 b 选择一条连续的子树范围
  • 如果给出 a=1,c=3 而没有固定 b，可以先利用 a=1 定位较大的区间，但 c=3 会分散在不同的 b 分组中，通常只能在扫描时过滤
  • 因此，最左前缀原则不是语法限制，而是联合键的物理排序决定了只有连续的前导列才能构成一次连续的树搜索范围

遇到范围查询为什么通常不能继续

  • 在 (a,b,c) 上，如果 a=1 且 b>3，可以定位到 a=1 分组中 b 大于 3 的连续后缀
  • 但在这个后缀中，c 的排序会在每个新的 b 值下重新开始，叶子顺序可能是 
    1
    (1, 4, 1) -> (1, 4, 3) -> (1, 4, 5) -> (1, 5, 1) -> (1, 5, 3) -> ...
  • 条件 a=1 AND b>3 AND c=3 需要从每个 b 分组中挑出 c=3，这些键之间夹着其它 c 值，不再是一个连续区间
  • B+树 的一次范围扫描只能从某个位置开始向后读取连续叶子，不能在同一条树路径上跳过每个 b 分组中的其它 c 值
  • 因此通常把 a 和 b 用于确定索引扫描范围，把 c=3 作为扫描过程中的索引条件或回表后的过滤条件
  • b>3 对应的不是一个具体 b 分组，而是多个 b 分组及其子页，每个子页内部都重新按照 c 排序
  • 如果还要让 c=3 参与树上的定位，就必须对这些子页分别搜索，搜索过程中反复回到父页选择其它子页，或者沿叶子链表扫描后再过滤，这已经不是一条连续的 (a,b,c) 范围
  • 从 B+树连续扫描范围的角度，通常会停止继续利用后续列的是 >、< 这类开放范围

为什么 >=、<=、BETWEEN 和前缀 LIKE 可以继续匹配

  • 这里的“继续匹配”是指后续列可以参与某个扫描边界的计算，不等于后续列在整个范围内都保持全局有序
  • >= 可以拆成 a=10 OR a>10，其中 a=10 这一段仍然按照 b、c 排序，因此 a>=10 AND b=20 可以从接近 (10,20) 的位置开始扫描，跳过 a=10,b<20 的无关键
    • 进入 a>10 的部分后，b 值仍然分散在每个 a 分组中，b=20 主要用于扫描过程中的继续匹配或过滤
  • <= 可以拆成 a<10 OR a=10，其中 a=10 是包含在结果中的等值端点，因此 a<=10 AND b=20 可以用接近 (10,20) 的位置作为上界
  • BETWEEN 10 AND 20 等价于 a>=10 AND a<=20，左右端点都包含，后续列可以帮助收紧两个端点，例如用 (10,20) 和 (20,20) 作为边界
    • 在 a 位于 10 和 20 之间的部分，b 仍会随着不同的 a 分组重新排序，因此后续列并不是把整个内部区间都变成等值查找
  • 前缀 LIKE 'abc%' 可以转换为从 abc 到下一个字典前缀之间的连续区间，左端点相当于包含了 a=abc 的等值边界，所以 LIKE 'j%' AND b=22 可以从接近 (j,22) 的位置开始扫描
    • 扫描到 name 大于 j 的其它前缀值后，age 不再全局有序，仍需要沿叶子链表继续读取并过滤
    • LIKE '%abc' 没有固定的起始前缀，不能用同样的方式定位
  • 与之相对，a>10 和 a<10 没有包含在结果中的等值端点，开放范围内部的后续列会在多个子页或分组中反复出现，通常只能由前面的列确定扫描范围
  • 因此，执行计划中的 key_len 或后续索引条件表示后续列参与了边界计算、索引条件下推或扫描过滤，不应直接理解为后续列在整段范围内都能继续二分定位
  • 判断最左前缀是否真正继续时，应区分两件事：索引是否用于定位扫描边界，以及扫描到索引项后是否还用索引键做过滤