B+-Tree的内部搜索：InnoDB的实现

在前面两篇文章，较为系统介绍了B-Tree和B⁺-Tree的基础。本文则以InnoDB为例，来看看B⁺-Tree内部排序的实现。

简单回顾B-Tree存储

在前面B-Tree基础文章中，我们了解到在一个B-Tree或B⁺-Tree的“节点”通常可以存放很多的“索引入口”。在数据库实践中，通常一个“节点”大小为16KB或8KB。一个索引入口的结构一般是：$ (k_i,p_i,\alpha_i) $ 、 $ (k_i,p_i) $、$ (k_i,\alpha_i) $，具体的，在叶子节点上通常为$ (k_i,\alpha_i) $，而非叶子节点则为： $ (k_i,p_i) $。

那么，在实际的设计中，一个“节点”可以存储多个“索引入口”，在非叶子节点，主要存储键值和到子节点的指针，即 $ (k_i,p_i) $；叶子节点中，则存储键值和相关数据，即$ (k_i,\alpha_i) $。

问题描述

在很多的B⁺-Tree实现中，一个节点可以存储几十、甚至数百个的“索引入口”。而我们在前面看到的示意图中，看起来节点内部的数据似乎是按照键值排好序的，但在实际实现中，这里以InnoDB的B⁺-Tree实现为例，问题要更复杂一些，主要考虑如下：

B⁺-Tree中的“数据”$ \alpha_i $可能是变长的，并且内容很大，例如200~300个Bytes。例如，在InnoDB的Clustered Index中，表结构是 id int, nick varchar(32),realname varchar(32),birthday date,password char(32),email varchar(60)，字符集是utf8mb4。
查询搜索是一方面，还需要更快的写入速度，从而提升数据库的事务吞吐量
依旧需要节点内部非常便利的顺序查找，以满足搜索、范围扫描等需要

以“堆”的形式存储

为了满足变长、快速存储的要求，InnoDB页面内部使用了典型的“堆”的形式组织数据，这也是数据库数据存储实现的一般模式。即，每次数据写入时，将数据存储在堆的“顶端”（或者中间的空洞），如右图：

对于最后写入的新记录$ (31,\alpha_5) $，不考虑排序，直接放在“堆顶端”
每条记录的大小不同，按“堆”遍历时，可以根据每条记录的元信息，到一条记录的头部（即本记录的尾部）

但在B⁺-Tree中遍历时，更多的是需要顺序遍历，例如键值搜索、范围查找等场景。那么，按“堆”存储的记录，就需要一种顺序遍历的方式。

B⁺-Tree页内搜索实现概述

逻辑实现说明

一种直观的思维是这样，在页面的某个特殊区域，新建一个“数组”（记录指针或偏移），顺序排列所有的记录。每次需要搜索时，则在该数据中进行二分或插值搜索。这种存储模式的优势是，简单而直接，且易于维护。但对于关系型数据库来说，如果数据写入或更新频繁，那么这个数组的维护会有非常频繁的数据拷贝。

InnoDB的实现（我后面要去看看Jim Gray的那本书，看看是否有描述这些细节）并没有使用这种直接的实现，而是做了一些变化：

在每条被存储的记录Header部分，都存储了按排序顺序的下一条记录的位置（页内偏移量），所以InnoDB的页内记录可以看做是一个按键值大小排序的链表
页面开辟了一片区域（Page Directory）存储“部分”页内记录的偏移，这些记录的选取与Skip List实现类似。即按排序顺序，并按一定的间隔取部分记录放到Page Directory中，并将Page Directory间隔两个记录之间在页内的所有记录称为一个Slot，Page Directory中的这条记录则可以称为一个Slot的Slot Header。

上右图是在GitHub上搜索到的由SmartKeyerror绘制的关于Page Directory的示意图^[6]，是比较准确且直观的。

所以，在进行搜索时（InnoDB的实现）：

首先，在Page Directory中的各个Slot Header中做二分查找
然后，再在Slot中进行线性搜索，即逐个向前比较

在InnoDB中，一个Slot有4~8个记录，所以，可以认为一个500条记录的页面，需要做的比较次数约为（考虑平均每个slot中6条记录）：

$$
log_2(\frac{500}{6}) + \frac{6}{2} \approx 9.38
$$

在实际中，可能会有多次CPU的Cache Miss发生，所以实际的成本比看起来的9.38次要略微高一些，但作为粗略预估，这个计算也是合理的。

InnoDB 物理存储实现说明

厘清物理层的实现，还是稍微花了一些时间的。在Jeremy Cole 2013 Efficiently traversing InnoDB B+Trees with the page directory 中对于Page Directory实现页内搜索做了比较详细的说明，并且在讨论中也一些有意思的讨论。但，对于其中的几个问题做了一些验证，还是有一些更细致的补充说明。

上面，SmartKeyerror绘制的关于Page Directory图在逻辑上是没有太大问题的，但就物理实现，则容易引起一些误解，故绘制了新的示意图如右下，以更准确的反映InnoDB物理存储的结构：

Page Directory就是一个存储页内偏移的“数组”，就是右图的深红色部分
每个slot使用2 Bytes，存储的是对应记录的页内偏移

相比于逻辑结构，物理结构上，需要注意的是：

“记录”在页内物理位置，并不是按键值大小排列，而通常是按照插入时间向下生长的
Page Directory存储在页面的底部，从高位地址向低位地址扩展；此外，Slot是InnoDB中的逻辑概念

InnoDB的代码参考

在了解Page Directory的过程中，还是阅读了部分InnoDB的代码，主要是innobase/page/page0page.c以及相关的代码。在该文件中，也有很多的注释可以阅读。这里列举部分函数，算是验证一下上述的部分理解。这里的示例代码来自版本：MySQL-4.1.7。

InnoDB 代码中的Page Directory

page0page.c 中的注释

这段注释在page0page.c文件中，是InnoDB最早、也是最为原始的关于page directory和slot的说明与介绍，非常建议阅读。

另外，这段注释中最后：50 x 4 bytes = 200 bytes这部分估算应该是有错误的，应该是50 x 2 bytes = 100 bytes。在16KB的页面中，2 bytes存储偏移量是够了的，而实际实现中也是2 bytes：

#define PAGE_DIR_SLOT_SIZE  2

当然，如果一定要“找补”，那么也可以把每条记录中用于存放slot中记录数量的4-bit也算进来的话，那么平均一个slot需要：

$$ 2+\frac{6*4}{8} \approx 5 $$

/*          THE INDEX PAGE
            ==============

The index page consists of a page header which contains the page's
id and other information. On top of it are the the index records
in a heap linked into a one way linear list according to alphabetic order.

Just below page end is an array of pointers which we call page directory,
to about every sixth record in the list. The pointers are placed in
the directory in the alphabetical order of the records pointed to,
enabling us to make binary search using the array. Each slot n:o I
in the directory points to a record, where a 4-bit field contains a count
of those records which are in the linear list between pointer I and
the pointer I - 1 in the directory, including the record
pointed to by pointer I and not including the record pointed to by I - 1.
We say that the record pointed to by slot I, or that slot I, owns
these records. The count is always kept in the range 4 to 8, with
the exception that it is 1 for the first slot, and 1--8 for the second slot.

An essentially binary search can be performed in the list of index
records, like we could do if we had pointer to every record in the
page directory. The data structure is, however, more efficient when
we are doing inserts, because most inserts are just pushed on a heap.
Only every 8th insert requires block move in the directory pointer
table, which itself is quite small. A record is deleted from the page
by just taking it off the linear list and updating the number of owned
records-field of the record which owns it, and updating the page directory,
if necessary. A special case is the one when the record owns itself.
Because the overhead of inserts is so small, we may also increase the
page size from the projected default of 8 kB to 64 kB without too
much loss of efficiency in inserts. Bigger page becomes actual
when the disk transfer rate compared to seek and latency time rises.
On the present system, the page size is set so that the page transfer
time (3 ms) is 20 % of the disk random access time (15 ms).

When the page is split, merged, or becomes full but contains deleted
records, we have to reorganize the page.

Assuming a page size of 8 kB, a typical index page of a secondary
index contains 300 index entries, and the size of the page directory
is 50 x 4 bytes = 200 bytes. */

从这里也可以看出来，因为InnoDB的页内地址很多地方是用的2 Bytes的存储偏移量，所以InnoDB单个页面大小也受此限制，最大为 $ 2^{16} \text{Bytes} = 64 \text{KB} $。（参考：innodb_page_size）

page_dir_get_nth_slot

该函数输入是一个页面指针，返回该页面的第$ n $个slot的指针。下右为InnoDB中的源码，下左则是代码部分对应的示意图：

Gets pointer to nth directory slot. */
UNIV_INLINE
page_dir_slot_t* page_dir_get_nth_slot(
            /* out: pointer to dir slot */
    page_t* page,   /* in: index page */
    ulint   n)  /* in: position */
{
    ut_ad(page_header_get_field(page, PAGE_N_DIR_SLOTS) > n);
    return(page + UNIV_PAGE_SIZE - PAGE_DIR
                    - (n + 1) * PAGE_DIR_SLOT_SIZE);
}

其他的优化

在 G. Graefe 2010 Modern B-Tree Techniques 中概述了B-Tree中使用Interpolation Search优化Binary Search的选择问题。关于这个问题，G. Graefe在另一篇Survey性质的论文中，较为系统的描述使用插值优化的一些相关技术：B-tree indexes, interpolation search, and skew.^[2]。

这篇论文^[2]介绍了很多使用插值优化二分查找的考虑，但对于InnoDB似乎并不适用，主要原因是，在InnoDB中很多的Key都不是整数，且Key的类型会比较复杂，例如字符串、多字段组合等，并没有很简单的插值计算。此外，在当前的InnoDB实现中，各个Slot并没有存储实际的Key值，而是存储Key所在的页内偏移，即如果要进行Key比较，则一定要跳转到页面的其他位置，而这与论文中的描述想避免CPU的Cache Miss的理念是冲突的。

一些遗留的问题：

一个slot的PAGE_DIR_SLOT_MAX_N_OWNED就是8，那么如果b-tree结构的相同key就超过8个，如何处理？（可能就直接截断就可以了，在搜索slot的时候需要注意处理这种情况）

B-tree indexes, interpolation search, and skew.

这是一篇研究B-Tree内部搜索性能的文章。B-Tree的最为主要的访问成本是从存储到内存，但作者认为，在某些场景下，需要关注CPU和内存处理的成本。这里的“某些场景”作者认为在变得更为重要，具体的，“某些场景”包括：

现在的内存变得很大，页面命中率变得非常高，只有很少的页面需要从存储读取
由于B-Tree的特性，页面读取的效率已经非常优秀了，已经是对数级的了

此外，作者还注意到：硬件技术的发展上，更多的是带宽的提升，而不是延迟的提升，这包括两个方面（磁盘到内存、内存到CPU）。

所以，作者把注意力放到了CPU处理效率的提升上。作者在论文中的预估是这样：在这个场景下，如果一个页面中有500个索引入口，那么页面内部的二分查找，就需要做：$ log_{2}500 \approx 18 $ 次比较操作以及对应的内存访问操作。

这里做过了一些初步的测试，在当代的CPU中，通常都会有32KB的L1 Cache ，故这里的部分事实已经不成立了。不过还是把这篇论文看完，看看作者的思考是什么。

相比于二分查找，插值查找则每次从区间的某个相对位置开始进行搜索，这个相对位置则使用插值的方式获得，而不是简单的从中点开始（二分查找）。如果，键值模型恰好是一个线性模型的时候，这个时候线性插值的效率就会非常完美。而现实中，确实很多就是线性分布的。这篇文章的目的：The topic and purpose of this paper is to survey techniques that avoid the worst case of interpolation search. 看看有哪些技术，避免差值查找的糟糕情况发生。

更细致的关于B-Tree和CPU Cache相关的讨论：[GL 01] G Graefe, P Larson: B-tree indexes and CPU caches. ICDE 2001, 349-358.

一些研究的方向：

最为直接的：使用一个类似的B-Tree结构，可能是二叉树、红黑树等
为了让这部分索引能够更快速，能够让其存放到CPU缓存中，会考虑删除前缀或后缀
此外，考虑利用B-Tree的多层索引，与CPU的多级缓存进行适配

阅读这篇论文的收获是了解大家考虑问题的方法，大家的思考方式，以及对各种技术边界的拓展。例如，

了解到大家对于程序实现的考虑，如何去思考处理器技术对于程序效率的影响，L1 Cache、L2 Cache以及指令Cache等如何影响CPU的效率。这些技术远看，其实并不算特别复杂，但是有了这些思考，对于计算机性能、架构的理解是不一样的。包括这里提到的一个论文中的观点：L1 Cache for Instruction 和 L2 Cache for Data 对于事务处理技术更为重要。这个观点就很有意思，当然，在当下，当然未必适用，但是这个思考方式可能是很重要的。如果对于这些技术非常了解，才有可能写出，诸如Redis、ClickHouse、DuckDB等这些性能非常极致的产品（大概是这样吧）。

再比如这两篇论文中的一些计算，可以看到如何考虑程序的效率，包括CPU时间、存储时间等。

在这里的一些考虑，看看他的计算和实现吧：在当时（这篇论文时候），一次$ \text{Page Access} $ 计为 $ 8ms $ ，传输时间为 $ 0.1ms $，如果页面中有 256 个索引入口。

考虑一个计算指标（ “utility” of a disk page ）即：

$$
\frac{\text{counter of comparison}}{\text{page access latency} + \text{page transfer time}}
$$

那么，256个入口，一个典型的二分查找需要约：$ \log_2{256} $ 次比较，则：$ utility = \frac{8}{8+0.1} = 0.987 $；

那么，如果页面大小增加到当前的八倍，那么需要的比较次数：$ \log_2{256*8} = 11 $，延迟依旧是 $ 8ms $ ，传输时间则为：$ 8*0.1 ms $，则：$ utility = \frac{11}{8+0.8} = 1.25 $

根据这里的计算，最优的页面大小，应该远远大于各个数据库系统中实际使用值。对于现代CPU来说，相比于处理指令，处理性能需要优先考虑cache miss以及pipeline stalls。在一些论文中对相关问题做了一些量化分析，有一些可以参考的结论，例如在事务处理时，最为重要的是L1的指令缓存和L2的数据缓存（[ADH 99].）。所以实现的主要考虑包括：代码量（具体的某个功能模块）的多少、复杂度，以及L2 Data Cache Miss。

页大小

概述：对于非叶子节点（尤其是靠近根节点的），使用非常大的页面大小是有一定道理的，但叶子节点则不应该页面太大。非叶子节点的使用率是非常高的，并且数量相比于叶子节点要少很多；但叶子节点，则不同。当需要读取某个叶子节点时，通常只是为了读取某一条记录（典型的OLTP场景），为了一条记录而读取过大的页面，会导致内存利用率的降低，反而会导致整体的性能降低。

在实践场景中，如果这个问题很关键或者有人对这个问题感兴趣，是可以做一些量化的分析的。把整个流程的时间、命中率、数据大小等相关的因素都考虑上，然后做一个最优化的分析。只是呢，B-Tree是一个比较古老的话题，大家对于这个数据结构的关注可能没有那么高了。

分裂和合并的选择

分裂与合并，不同的实现会有一些不同选择，包括：

提前分裂，例如页面的占用率超过了一定的比率就进行分裂；结合插值算法考虑，如果页面里面的值，可以非常好的分裂为两个非常适合插值的区间，也可以考虑优先进行分裂。
在某些实现中，删除的时候，从不触发合并，而是在某种“碎片整理”的时候才进行合并或分裂处理

回退到二分查找

在数据分布非常倾斜的情况，插值查找的效率可能会非常糟糕。需要考虑回退到二分查找。一些常见的策略是这样：

例如，进行了3、4次差值查找还没有找到目标，那么可以回退到二分查找
可以考虑根据第一、二次查找的效率做一些预估，预估效果差，则回退到二分查找
在差值查找中，考虑使用二分查找做一些修正，最终后再退回二分查找

正规化处理

当key是字符串的时候，通常需要考虑先进行一定的正规化处理，以可以更好的进行大小比较。
前缀删除。和一般的索引/搜索技术一样，如果有公共前缀可能会大大降低效率。

回归差值

在进行了一些插值计算后，可以考虑使用这些值进行回归计算。

名词说明

B+Tree、B+-Tree 均指B⁺-Tree
一般的，B-Tree指狭义的、经典的B-Tree，该结构主要参考：了解 InnoDB 的索引结构：B-Tree 基础
有时候，B-Tree也会指代B⁺-Tree或其他B-Tree变种；这种用法也是非常广泛的，例如，在MySQL/InnoDB的文档中，仅使用B-Tree，而更为准确的说是B+-Tree
“节点”（Node）、“页面”（Page）、“数据块”、“块”(Block)等均指存储B-Tree或B⁺-Tree的节点，即树结构的节点，内部可以存储多个键值。在不同的语境下，大家会用不同的词，例如通常在算法课程/书籍中，会更多的使用“节点”（Node）；而在数据库实现中，则更喜欢用“页面”（Page）或“块”(Block)；更为细节的，如果在内存中，则更多的时候用“页面”（Page），在磁盘上，则更多的“块”(Block)。各种情况下混用的也很多，并没有什么问题。
“记录”（record）、“行”（row）、tuple都是表示表中的一行记录，通常包含多个字段数据。
索引入口（Entry）等是指完整的“键值对”，在叶子节点中，通常包括$ (k_i, a_i) $；在非叶子节点中可能的形式是：$ (k_i,p_i, a_i) $ 或 $ (k_i, p_i) $
TAOCP 是 “The Art of Computer Programming”的缩写

参考

本文主要参考内容为：

[1] G. Graefe 2010 Modern B-Tree Techniques in Foundations and TrendsR in Databases Vol. 3, No. 4 (2010) 203-402c 2011 DOI: 10.1561/1900000028
[2] Goetz Graefe. 2006. B-tree indexes, interpolation search, and skew. In Proceedings of the 2nd international workshop on Data management on new hardware (DaMoN ’06).
[3] 2004 Innobase Oy InnoDB Source Code / MySQL 4.1.7 (Created 2/2/1994 Heikki Tuuri)
[4] Jeremy Cole 2013 Efficiently traversing InnoDB B+Trees with the page directory Blog Posts
[5] Calvin Sun(Senior Manager, Twitter) 2013 InnoDB Internals DTCC topic in China
[6] SmartKeyerror 2021 InnoDB-Page.pdf Draw at GitHub

orczhou.com

B⁺-Tree的内部搜索：InnoDB的实现

简单回顾B-Tree存储

问题描述

以“堆”的形式存储

B⁺-Tree页内搜索实现概述

逻辑实现说明

InnoDB 物理存储实现说明

更多关于Page Directory实现细节

InnoDB的代码参考

InnoDB 代码中的Page Directory

page0page.c 中的注释

page_dir_get_nth_slot

其他的优化

一些遗留的问题：

B-tree indexes, interpolation search, and skew.

页大小

分裂和合并的选择

回退到二分查找

正规化处理

回归差值

相关性分析

名词说明

参考