从 PostgreSQL 源码深入理解 BTree 索引

引言

BTree 在数据库领域中是一种最重要的索引结构，但是对于初学者来说，并不容易理解其运行原理。即便大致了解其原理，也只是停留在表面上的死记硬背，无法深入其细节。导致：

1. 工作中无法灵活运用 Btree 索引对数据库操作进行优化。
2. 面试时不能清晰的说明 BTree 索引细节原理。

网上讨论 BTree 索引的文章很多，但是大多数都集中在表面，并没有深入源码层面进行解析。导致初学者似懂非懂，无法掌握 BTree 索引设计的精髓，更无法对其融会贯通。

本文虽然以 PostgreSQL 数据库举例，其大部分结论也适用于其他数据库。接下来按照下列顺序介绍 BTree 索引。

1. BTree 索引的性质。
2. BTree 索引的结构。
3. BTree 索引的常见操作。

本文主要适合后端开发、数据库运维等人员阅读。

注意：

1. 文中说的 BTree 就是 B+Tree。
2. 文中以 PG 代替 PostgreSQL 称呼。
3. 本文不涉及 PG 数据库的安装。
4. 本文假设读者具有 BTree 的基础知识。

PostgreSQL BTree 索引

PostgreSQL 介绍

PG 作为最先进的开源关系型数据库（官网语： PostgreSQL: The World's Most Advanced Open Source Relational Database），在全球范围内被各个行业广泛使用。又因其友好的开源协议、严谨代码风格、学院派的优秀设计、完全兼容 sql 规范等优点被各个厂商二次开发，众多的数据库内核开发者以其为典范进行深入学习。严谨代码风格、全面文档、详细的代码注释，都使得我们非数据库内核开发人员能够一睹工业界非常优秀的 BTree 索引的实现。

PostgreSQL BTree 索引

本文基于最新的 PG 16 的代码，在 GitHub 下载，地址为 postgres/postgres at REL_16_STABLE。

PG BTree 索引基于 Lehman and Yao 的论文 Efficient Locking for Concurrent Operations on B-Trees 来实现。在源码文件 src/backend/access/nbtree/README 中论述。相比经典的 BTree 结构实现，Lehman and Yao 增加了两个结构。

1. 同级节点增加指向右边节点的指针。
2. 节点中增加节点中所有数据的上限 high key 。

上面两个结构使得 PG BTree 索引能够检测到节点的分裂，并且在搜索时，只需要获取单个节点锁，大大增加了 Btree 索引的并发性能。

BTree 索引的性质

PG BTree 索引有下列性质。

1. 可排序（can_order），即索引结构中的数据是有序的。BTree 作为搜索树的一种，天然满足此条件。
2. 可唯一 (can_unique),支持索引唯一和作为主键索引。
3. 可以组合索引 (can_multi_col)。支持多个列作为索引。

其他性质可包含（can_include）和可不包含 (can_include) 不做介绍。BTree索引的优秀特性使得众多数据库作为索引的创建时的默认实现。

可以通过下面的命令在 pgsql 中查询索引特性。

SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name) 
FROM 
pg_am a, 
unnest(array['can_order', 'can_unique', 'can_multi_col','can_exclude', 'can_include' ]) p(name)
WHERE a.amname = 'btree';

数据准备

本文数据库来自 demo-small-en，下载压缩包解压。参考 Postgres Pro Standard : Documentation: 10: J.1. Installation : Postgres Professional 导入数据。

使用 psql 查询相关数据。

可以看到 bookings_pkey 索引就是 BTree 类型的索引。我们以此为例解释 BTree 索引的结构。

Indexes:
    "bookings_pkey" PRIMARY KEY, btree (book_ref)

注意：我的数据名称改成了 demo_small。

BTree 索引结构

BTree 物理存储位置

在 PG 中索引和普通表的存储逻辑是一样的，在 PG 中叫做 relation，可以通过下面的命令查询。

还需要查询 pg 的 PG_DATA 目录。

将上面信息组合起来，在我的电脑中，索引文件信息如下。

安装插件

安装 PG 插件 pageinspect，此插件可以用于解析探索 BTree 索引文件内部结构。

create extension pageinspect;

使用可视化插件

下载 pageinspect_inspector: A little tool to display your postgres BTree indexes in an html using pageinspect data 插件。

项目目录下执行 sudo python setup.py develop 安装 python 包，然后执行下面的命令。

python3 inspector/command.py --host 127.0.0.1 --port 5432 --db demo_small --user  postgres --password postgres --index bookings_pkey --path renders.html

将其中 PG 相关的信息替换成你自己的配置，renders.html 是最后生成的文件名称，使用浏览器打开。注意：由于数据量很大，26万多，所以生成文件很大，浏览器不一定能打开，可以多次尝试。如果最终还是打不开，可以尝试删除部分数据，并且重建索引，再次运行上面的命令。

可视化索引如下图所示：

BTree 索引结构

从上面的图可以清晰地看到 PG 的 page （即 BTree 节点，一个 page 通常是 8k ，在 pg 编译时确定）分成四种类型。每一个索引 page 都有一个 page block number唯一标识索引 page。page level 是以 0 开始向上层节点递增。page high key 是指 page 中的索引索引 key 都严格小于它。

1. Meta Page：Meta page 总是 BTree 索引的第一页。它包含 Btree 索引的版本、高度、root page 等信息。至于 Fast root 用来加速 BTree 索引的搜索。例如，对于上图中的结构，假如 root page 只有一个子节点，那么搜索可以直接从 parent page 开始（减少一次磁盘 io）。那么在 meta page 中，Fast Root block number 为 289，Fast Level 为 1。

2. Root Page：BTree 的根 page，常驻在内存中，BTree 的搜索通常此 page 开始。

3. Parent Page：Btree 的中间节点，有父节点和字节点。

4. Leaf Page：BTree 的叶子节点，真实存储索引对应的行数据信息，在 PG 中即为 ctid。例如 ctid = （2，5） 表示此行存储在表文件的第2个数据叶的第5个相对位置。详细信息可以参考 1.4. The Methods of Writing and Reading Tuples。

BTree 索引搜索举例

本小节使用插件 pageinspect 跟踪下面 sql 在 Btree 中搜索逻辑。

select * from bookings where book_ref = '65BECA';

从索引结构的可视化图可以看到65BECA 是 page block numer 为 287 的 leaf page 的 page high key。 由page high key定义可以知道，65BECA 对应的索引 key 存储在 page block numer 为 288 的 leaf page 中。接下来使用 pageinspect 进行验证。

注意：图中 leaf page 的 page high key 有问题。page block numer 为 287 的 leaf page 的 page high key 应为 65E1E1。学习了后面的知识可以通过下面的方式查询，每个 page 的第一个元素为 page high key。

首先查看 meta page 的信息。

查看 root page 的信息。

上图中的 ctid 指向的是子节点的 page block numer。图片中 data 数据是 16 进制显示的，临时写一个函数解析这些数据。

CREATE FUNCTION data_to_text(data text) RETURNS text  
AS $$  
DECLARE
    raw bytea := ('\x'||replace(data,' ',''))::bytea; pos integer := 0;  
    len integer;  
    res text := '';
BEGIN  
    WHILE (octet_length(raw) > pos) 
    LOOP
        len := (get_byte(raw,pos) - 3) / 2; 
        EXIT WHEN len <= 0;  
        IF pos > 0 THEN
            res := res || ', '; 
        END IF;
            res := res || (  
            SELECT string_agg( chr(get_byte(raw, i)),'') FROM generate_series(pos+1,pos+len) i
            );
            pos := pos + len + 1; 
    END LOOP;  
    RETURN res;
END;  
$$ LANGUAGE plpgsql;

使用函数之后，再次查询第 290 页，查询结果如下图所示。

由于 652CB6 ⩽ 65BECA < CA5FE3，我们继续查询第 289 页。

由于 6585C3 ⩽ 65BECA < 65E1E1，我们继续查询第 287 页，此页为 BTree 索引的叶子节点。

x 通过 ctid (666,1) 在 bookings 表中查询。

至此我们成功查找到目标数据。遍历的 page 路径为：290-> 289 -> 287 -> bookings 表。如果 root page 在内存中，需要经历三次磁盘io。BTree 的搜索路径下图红色路径所示。

BTree 源码分析

前面小节通过 PG 的插件和可视化的方式介绍了 BTree 的搜索过程，让我们对 PG BTree 的结构和搜索逻辑都了大致的了解。接下来我们通过对源码的介绍，更加深入的理解 BTree。阅读源码时需要注意以下几点：

1. 明确目的，可以通过网络查找目的代码的主要文件和函数。
2. 抓住主要逻辑，忽略旁枝末节。
3. 阅读 PG 代码，需要一定的 C 语言基础。
4. 需要一定的英语基础，理解代码相关注释。

首先通过伪代码形式，介绍主要逻辑，然后逐步详细介绍相关的源码。

BTree 查找源码

BTree 伪代码逻辑如下，逻辑很简单根据条件遍历 BTree ，实际的源码并不简单。

Page = page = getroot_page();
for(;;){
    page  = findNextPage(page);
    if(page is leaf page)
        break; //find target leaf page
    else
        //continue for loop
}

BTree 查找源码在 src\backend\access\nbtree\nbtsearch.c ，函数签名如下：

BTStack _bt_search(Relation rel, Relation heaprel， 
    BTScanInsert key, Buffer* bufP, int access, Snapshot snapshot)

参数介绍：

1. rel，包含索引信息，例如索引文件的位置，索引的定义等。
2. heaprel，包含索引所在表的信息。
3. key，搜索条件的信息，例如搜索的键值，搜索的操作符等。
4. bufP，传出参数返回给调用者，是最终 key 所在的叶子节点（如果命中的话）。
5. access，代表是读搜索还是写搜索。如果是写搜索，当 root 节点不存在时，会创建。
6. snapshot，事务控制，与 PG 的 mvcc 的是实现有关系，暂且不关注。
7. BTStack，函数返回值，代表本次搜索遍历的所有

获取 root page

//function: _bt_search
/* Get the root page to start with */
*bufP = _bt_getroot(rel, heaprel, access);

获取 root page 的逻辑如下

Buffer _bt_getroot(Relation rel, Relation heaprel, int access)
{
    //如果有缓存并且缓存有效，直接返回
    if (rel->rd_amcache != NULL)
    {
        /* OK, accept cached page as the root */
        return rootbuf;
    }
   //根据索引元数据信息获取索引 meta page
   //BTREE_METAPAGE = 0 表示 meta page 在索引文件的第一页也就是文件的最开头
    metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
    metad = _bt_getmeta(rel, metabuf);
       
    //如果 root page 没有初始化，则初始化
    if (metad->btm_root == P_NONE)
    {
        //创建根节点
        rootbuf = _bt_allocbuf(rel, heaprel);
        rootblkno = BufferGetBlockNumber(rootbuf);
        rootpage = BufferGetPage(rootbuf);

        //保存根节点信息到 meta page 中
        metad->btm_root = rootblkno;
        metad->btm_level = 0;
        metad->btm_fastroot = rootblkno;
        metad->btm_fastlevel = 0;
    } else {
        //正常获取 root page
        rootblkno = metad->btm_fastroot;
        //缓存 meta page
        rel->rd_amcache = MemoryContextAlloc(rel->rd_indexcxt,
                             sizeof(BTMetaPageData));
        memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
        
        rootbuf = metabuf;
        for (;;)
        {
            rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
            rootpage = BufferGetPage(rootbuf);
            rootopaque = BTPageGetOpaque(rootpage);
            //找到有效的 root page 可以返回了
            //这里涉及到 BTree page 删除的逻辑，需要判断获取 page 的状态
            if (!P_IGNORE(rootopaque))
                    break;
            //根据右指针获取下一个 root page（当前 root page 是无效的）       
            rootblkno = rootopaque->btpo_next;
        }
    }
    //最终获取加了读锁的 root page
    return rootbuf;

查找主体逻辑

在获取到 root page 之后，就进入到 BTree 索引查找的主体逻辑中。

//获取根节点
*bufP = _bt_getroot(rel, heaprel, access);

for (;;)
{
    //是否需要，向右查找兄弟节点
    //这是因为节点会发生分裂，目标搜索 key 可能会被分配到右边的兄弟节点
    //后文会详细介绍此函数
    *bufP = _bt_moveright(rel, heaprel, key, *bufP, (access == BT_WRITE),
			stack_in, page_access, snapshot);
    
    //如果节点是叶子，则结束循环。这是循环的唯一出口
    page = BufferGetPage(*bufP);
    opaque = BTPageGetOpaque(page);
    if (P_ISLEAF(opaque))
        break;
     
    //使用二分查找在 page 中查找合适的位置
    offnum = _bt_binsrch(rel, key, *bufP);
    itemid = PageGetItemId(page, offnum);
    itup = (IndexTuple) PageGetItem(page, itemid);
    Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace);
    //找到字节点对应的 page number
    child = BTreeTupleGetDownLink(itup);
    
    //找到子节点对应的 page 进入下一次循环
    *bufP = _bt_relandgetbuf(rel, *bufP, child, page_access);
    
    //用于保存当前的搜索页面的 page num 和 叶内偏移
    new_stack = (BTStack) palloc(sizeof(BTStackData));
    
    //这里以前文介绍的搜索举例，最后的结构是
    //287 -> 289 -> 290
    stack_in = new_stack;
}
    //返回
    return stack_in;
    
    //注意：函数签名中 bufP 指向最终的叶子节点。

_bt_moveright 函数

此函数主要是为了解决并发问题。以前文提到的搜索路径为例 290-> 289 -> 287。当进程 A 在 290 page 上搜索时返回子节点为 289 page，但是此时进程 A 对 289 page 并没有加锁。如果此时进程 B 正在对 289 page 添加节点导致节点分裂，分裂成 289 和 300（假如），而且恰好查找的目标 key 的范围被分配到 300 page，就需要执行 _bt_moveright 操作来修正我们的查找路径。

for (;;)
{

  //如果已经是同层级最右边的节点，结束循环
  if (P_RIGHTMOST(opaque))
      break;
  
  //如果是写操作的查找，并且当前节点正在分裂则帮助其完成分裂
  if (forupdate && P_INCOMPLETE_SPLIT(opaque)){
      //
  }
  
  if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval)
    {
        //释放当前节点的锁，获取其右边节点 opaque->btpo_next 并且加读锁
        buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
        continue;
    }

  //最终返回
  return bufp;
}

以上从源码级别介绍了 Btree 的查找逻辑。

总结

限于篇幅原因，源码级别调试和 Btree 的删除逻辑写在后面的文章。本来从 PG 数据库入手，从可视化的图片以及源码层面介绍了 Btree 逻辑结构，物理结构，让读者可以深入理解 Btree 的实现。

参考资料

1. 1.4. The Methods of Writing and Reading Tuples :: Hironobu SUZUKI @ InterDB

2. PostgreSQL's indexes – BTrees internal data structure | Louise Grandjonc, Python/SQL developer but also a human (louisemeta.com)

3. louiseGrandjonc/pageinspect_inspector: A little tool to display your postgres BTree indexes in an html using pageinspect data (github.com)

4. postgres/postgres at REL_16_STABLE (github.com)

5. PostgreSQL 14 Internals : Postgres Professional