【2】MySQL 为什么使用 B+树

配套视频在 B 站观看MySQL 的 InnoDB 使用 B树组织常见的索引。理解这个选择不能只记住“树矮、查询快”数据库既要找到某一条记录也要按顺序读取一批记录还得考虑数据在磁盘和内存之间怎样搬运。本文以 MySQL 8.4 的 InnoDB 为例沿着同一张订单表讲清三件事怎么找到页索引项如何把订单号指向数据所在的页。怎么找到记录页进入内存后页目录和记录链怎样配合查找。怎么接着查叶子页之间的链接为什么适合范围查询。图 1后台给出订单号 66数据库需要找到这条订单。右侧索引把订单号与记录所在的页联系起来。查 66 号订单先得知道它在哪一页在网店后台点开66 号订单想看看发货没有。后端交给数据库的查询可以简化为SELECTid,amount,statusFROMordersWHEREid66;这里假设id是主键。我们只讨论它如何沿主键索引定位记录不展开 SQL 的解析、优化和事务可见性判断。以独立表空间为例这张表的数据和索引存放在orders.ibd中。文件被划分为许多页InnoDB 索引页的默认大小是16 KB页面大小在实例初始化时配置。不是每张表在所有配置下都单独对应一个.ibd文件。参见独立表空间和索引的物理结构。图 2a文件中的部分页。有的页放索引项有的页放订单记录页号与订单号是两种编号。图 2b展开 12 号页里面包含订单 6471并高亮 66。每页八条订单只是示意不是实际容量。66 号订单在12 号页里。但查询一开始只有订单号 66并不知道页号 12。先设想没有按键定位的索引只能检查一个个页、比较里面的记录。表越大要排查的数据就越多。这是为了说明索引的用途实际 InnoDB 表始终有聚簇索引即使没有显式声明主键也会选择或生成聚簇键。索引项怎样把订单号指向页给子页配上一条键值边界和子页号再把这些索引项放进上层页就能先判断目标属于哪个范围。例如下图中 9 号索引页包含这样两条相邻索引项64 → 页 12这一分支从边界 64 开始。72 → 页 5下一分支从边界 72 开始。因为64 ≤ 66 72查询应沿第一条分支去 12 号页。64 是用于比较的键值12 是子页号两者不能混为一谈。图 3完整的索引结构查询路径是页 3 → 页 9 → 页 12。未命中的分支保留在原位置无须逐一读取。如果索引项越来越多一页放不下就把它们分到多个索引页上面再设一层索引。这样逐层组织就得到一棵树内部页保存用于导航的索引键和子页号。叶子页保存索引记录本例是主键对应的聚簇索引叶子里保存订单行数据。所有叶子处于同一层页分裂等操作会维护这种平衡。这就是本例使用的B树。查 66 时从根页选中 56 这一分支到 9 号页再选中 64 这一分支到 12 号页。并不需要先把全部索引页读一遍。图中的边界恰好取了子页的最小订单号便于观察。实际 InnoDB 内部项使用能区分范围的索引键前缀还包含最左分支的特殊标记发生删除后边界也不要求总等于叶页现存的最小键。具体定义见 MySQL 8.4.0 的节点指针说明。为什么要多路分支还不在内部放订单详情二叉搜索树的每个节点最多指向左右两个子节点。即使保持平衡记录多了路径仍可能较长。数据库以页为单位组织数据如果沿途所需页不在缓存中还需要从磁盘读入。一页能容纳多条索引项就可以指向很多个子页。每一层能排除更多无关数据同样规模的数据通常只需要较少的层级。这里比较的是组织方式不是把二叉树的每次比较都算作一次读盘。多路分支也并非 B树独有经典 B树同样具备这个特点。两者的另一个区别是经典 B树的内部节点也可保存实际记录B树把实际记录集中在叶子。下面两图单独比较内部页的容量不是在改造前面的订单索引。比较时保持页大小、键和指针宽度相同叶子范围另作示意条目数不代表固定倍率。对照结束后仍回到页 3 → 页 9 → 页 12 的查询路径。图 4a经典 B树的容量示意。内部节点同时保存实际记录和导航所需信息。图 4bB树把实际记录留在叶子内部页可以容纳更多分支。订单详情越占空间能放进同一页的导航项就越少。把详情留在叶子内部页可以容纳更多分支通常有利于降低树高和潜在的读页成本。这不是说 B树在任何数据量下都比 B树少一层也不是说 B树查询一定慢。B树可能在内部节点直接命中记录B树通常要沿路径走到叶子。B树的优势要和后面的范围读取一起看。三层 B树不等于每次读三次磁盘继续看页 3 → 页 9 → 页 12这条路径。树给出了应该访问哪些页但这些页不一定都要从磁盘读取。InnoDB 在内存中维护Buffer Pool缓冲池数据页和索引页都会被缓存。需要一个页时先查缓冲池已有可用的页就直接使用没有才安排读入。见 Buffer Pool 官方说明。图 5两种缓存初态并列展示。三页都没缓存时需读入 3 页根页已缓存时需读入 2 页。这里统计本路径需读入的页不统计实际设备请求数。因此要分清两个问题树有几层决定根到叶路径经过多少层页。实际需要读盘多少还受缓冲池命中、预读等因素影响不能只看树高。B树尽量减少需要经过的层级缓冲池则尽量让常用页留在内存。它们作用不同也会共同影响一次查询的代价。到了 12 号页怎样找到 66 号记录现在需要的页已经在内存里。12 号页里仍然有多条记录数据库还得在页内定位 66。页的内部不只有行数据还包含页头、空闲空间、页目录等信息。页目录不是上面那棵树的索引页它只帮助查找当前页中的记录。本页的记录先通过记录头中的下一条记录指针按主键顺序串成链。页目录再按组管理这条链目录槽指向各组的末条记录而不是每条记录各占一个槽。以图 6 的订单为例6467 分成一组目录槽指向组尾 67。查 66 时先在目录槽中二分确定它落在这一组再沿记录链定位。图中只展开这次查找用到的目录槽其他槽作了省略。目录槽指向组尾 67但沿“下一条记录”指针不能从 67 退回 66因此要从前一个目录槽指向的记录出发沿链向后查。这里的前一个槽指向系统起点infimum。它不是真实订单只是这条链的起点从它向后才依次遇到 64、65、66。图 6完整的 12 号页示意。左侧保留记录的物理位置右侧展开本次要查的一组页格式、分组和目录槽作了简化。图 6 局部放大“起点”和组尾 67便于认清两个目录槽。原图蓝线作了简化不表示两个槽都指向记录 67也不表示查找顺序。查 66 时从“起点”对应的 infimum 出发沿记录链依次经过 64、65、66这段链路未在局部图中画出。完整画面仍见上图。沿链比较到 66就找到了订单。叶子记录中保存金额128 元、状态已发货等行数据查询可以据此返回结果。要注意逻辑有序不等于记录在页内的物理位置连续。图中 64、65、66 的实际存放位置可以分开查找依靠的是记录链的顺序而不是图上从上到下的位置。页目录槽和分组的定义见 page0page.h目录二分与沿链查找的衔接见 page0cur.cc。查 6675 号订单叶子链就用上了单条订单查到了现在改成按订单号导出一批数据SELECTid,amount,statusFROMordersWHEREidBETWEEN66AND75ORDERBYid;索引先定位起点 66。12 号页包含 6471取完 6671 后还需要 7275。B树的叶子页之间有前后链接查询可以继续访问5 号页从 72 读到 75遇到超过上界的 76就可以结束这段范围扫描。不用为了每条后续记录都重新从根开始定位。图 7两张叶子页按键值顺序相连。先在页 12 取 6671再沿下一页链接到页 5 取 7275页号和文件位置不必连续。图中的 n 是记录总数k 是扫描的结果数复杂度不等于读盘次数。叶子页按键值顺序相邻和它们在文件中是否物理相邻是两回事。沿叶子扫描减少了反复向上导航的需要但不代表整段范围一定只发生一次磁盘顺序读取。二叉搜索树和 B树也能做范围查询。二叉搜索树可以按中序后继继续经典 B树的实际记录分布在内部节点与叶子中遍历时也要考虑内部记录不能只把叶子串起来就当作取全了结果。它们都不必为每个结果从根重查。B树把实际记录集中在同一层叶子中定位起点后就能沿叶子组织有序扫描。相比之下哈希索引不提供这种有序后继不能直接利用哈希结构完成同样的范围扫描或排序这是选择索引结构时需要考虑的差异。见官方 B树与哈希索引比较。页满了索引也要调整查询方便不代表写入没有成本。假设继续插入88 号订单。沿图 3 的导航56 ≤ 88 100先进入 9 号页再根据其中不大于 88 的最大边界 80沿80 → 页 19进入 19 号页。该页当前存有 8087 号订单。如果页里已经没有足够空间可能需要分裂分配新页、移动部分记录并调整父页中的索引项和相关链接。父页如果也满了调整还可能向上继续。图 8a分裂前80 → 页 19页 19 中是订单 808788 尚待写入。假设本页已经没有足够空间。图 8b一种可能的分裂结果。父页保留 80 → 页 19蓝底新增右侧的 84 → 页 24新页是 24并维护叶子链接。实际分裂位置取决于实现和插入情况不保证对半分也不是每次插入都会分裂。图中 8083 留在 19 号页8488 放到新页 24。父页增加84 → 页 24后再定位 88 就会沿这一新分支找到它。叶子链接也随之调整范围扫描仍能从页 19 接着读页 24。页分裂是在维护原有结构记录仍按键序组织上层仍能找到对应子页叶子仍处于同一层。键值和页数的变化需要付出额外的空间与写入开销。叶子里是不是总有完整的订单前面的例子一直按主键id查找所以落到的是聚簇索引的叶子可以取得行数据。但这不能套用到所有索引。在 InnoDB 中二级索引的叶子通常保存索引列和对应的主键值。例如按用户号找到一条二级索引记录后可以取得订单号 66如果需要的金额、发货状态不在该索引中就还要用 66 去聚簇索引找行数据这一步通常称为回表。图 9左侧是主键聚簇索引的叶子右侧是二级索引的叶子。二级索引先提供主键 66所需列不在其中时还要用 66 查聚簇索引。列已覆盖时不必为补列回表。如果查询需要的列已经在二级索引里就可能通过覆盖索引完成查询无须为了补齐这些列再回表。这里解释的是列是否齐全事务可见性等检查还有自己的规则。具体结构见聚簇索引与二级索引。总结再看 66 号订单这次查询上层索引按键值边界选页缓冲池提供所需页页目录和记录链在页内定位记录。改成 6675 的范围查询就在定位起点后沿叶子继续读取。InnoDB 选择 B树主要是让这些工作配合起来内部页只保留导航所需的信息一页可以指向较多子页叶子保持等深实际记录集中在叶子并能按键序接续扫描。它适合以页组织的数据也兼顾单点定位与范围读取。树高不等于固定读盘次数叶子链不保证物理连续索引也需要为分裂等维护付出代价。把这些边界一起记住比只背一句“B树查询快”更接近它的实际作用。作者风火嘟嘟。本文由同题视频整理为图文观看视频。页号和订单数据用于解释结构未据此进行容量估算或性能测试。