Btree索引插入流程分析
专栏内容：
- postgresql内核源码分析
- 手写数据库toadb
- 并发编程
开源贡献：
- toadb开源库
个人主页：我的主页
管理社区：开源数据库
座右铭：天行健，君子以自强不息；地势坤，君子以厚德载物.
前言
B树索引在PostgreSQL中得到了广泛应用，它是一种自平衡树数据结构，可以维护有序数据并允许进行搜索、顺序访问、插入和删除操作。在PostgreSQL中，可以在任何数据类型上使用B树索引，支持排序，支持大于、小于、等于、大于或等于、小于或等于的搜索。
B树具有一些重要的特征。首先，B树是平衡的，每个叶子页与根都由相同数量的内部页分隔开，因此搜索任何值都需要花费相同的时间。其次，B树是多分支的，每个页面通常包含许多（数百个）ctid，因此B树的深度很小，对于非常大的表，实际上可以达到4-5的深度。最后，索引中的数据按非递减顺序存储（在页面之间和每个页面内部），并且同一级别的页面通过双向列表相互连接，因此不需要每次都返回到根，可以通过遍历链表获取一个有序的数据集。
PostgreSQL中的B树索引是一种高效的数据结构，可以用于加速对有序数据的搜索和访问。通过使用B树索引，可以大大提高数据库的性能和响应时间。
概述
本文主要介绍postgresql 中常用的索引类型btree的插入过程，通过本文对postgresql 索引查询的代码有一定了解，希望能够帮助基于postgresql做内核开发的同学，当然理解也有限，正在看这部分的同学可以在评论区一起来探讨。
插入流程
在进行SQL语句 insert一条数据行时，如果某一列带有索引，那么在插入数据的同时，也需要插入一条索引项；
索引项中需要记录数据行的tid，也就是位置信息，所以插入索引的时机，是在插入数据行成功后，使用数据行的位置信息生成一条索引项，然后进行索引项的插入流程；
索引项的插入整体流程如下：
- 生成新的索引项；
- 检查唯一性；
- 查找合适的插入位置；
- 对待插入索引页面检查空闲空间是否足够；
- 如果空间不足，则将当前索引页面进行分裂为左右两半；
- 然后将新索引项加入左或右页面；
准备阶段
生成一个索引项，这就是需要插入的新索引项；
先是遍历btree树，从root中的元组进行二分查找，找到该索引项对应的范围所在的下层的节点的pageno，如果层级较多，每次都是如此，最终找到叶子节点，找到要插入的叶子节点的索引数据块；
检查唯一性
对于主键的列，需要检查索引的唯一性，避免插入两条相同的索引；
对于主键肯定是需要唯一的存在，为什么要在这里做唯一性检查，而不是在数据插入时检查呢?
因为在插入数据时，如果检查唯一性，还是要通过索引扫描来比对，所以直接放到索引插入阶段，当索引检查不通过时，那么前面插入的数据也是无效的。
- 检查时，在索引树中先找到相同值的位置；
- 然后对比它的tid是否一样，如果不一样，也就是除了之前新插入数据之外还有一条相同字段的数据存在；
- 检查相同索引项对应的数据行的事务是否提交； 如果没有提交，则等待该事务结束，再进行检查；
- 如果相同索引项对应的数据行的事务已经提交，那么就产生了冲突；
- 当有冲突时，就会报错，abort当前事务，也就会导致前面插入的数据无效；
查找合适的插入位置
在前一步已经找到了符合的叶子节点，在 _bt_findinsertloc 中，还需要进一步查找合适的位置，主要有以下几种情况：
- 对于非heapkeyspace的索引，相同键值索引项，需要插入到最右边；此时要向右查找节点；
- 对于多个索引页面都有相同highkey，也就是重复值，那么这些页面都适合插入新值，找一个空间足够的即可；
- 还有一种情况是，对于数据多版本需要跨页时，要新增索引项，此时索引项的值是不变的，只是对应的tid发生了变化；对于这种情况，可以先检查删除的dead索项，避免索引的分裂；
在上面向右查找的情况，postgresql做了一些优化，综合了向右找的代价，和提前分裂的代价，有概率提前分裂；
对于新插入的索引项，不能大于空闲空间的三分之一;
检查空闲空间
在 _bt_insertonpg 调用中，实现了剩余空间检查，页面分裂，索引项的真正插入；
当前查找到索引页空间小于当前新索引项时，就需要进行索引页的分裂；
如果空间足够，则直接插入即可；
页面分裂
Btree的页面分裂是插入环节中的关键点，也是难点所在；在这个环节中，因为会修改多个节点页，对并发访问影响比较大，postgresql在这里做了一些优化；
我们先按常规思路来模拟一下分裂的过程；
某一节点分裂成左右两个节点，将旧节点的内容平分到新节点中，然后变更左节点的后续链接，变更右节点的前续和后续链接，将它中加入本层的双向链表，最后将新增节点信息加到父节点中；
这样一个分裂的过程中，所有变更节点都需要加互斥锁。在btree查找章节中已经介绍过，上下层之间是单向的，也就是只能从父节点找到下层节点，为了避免重复查找父节点，在确定插入节点时，就已经将路的层次路径记了下来；
下面我们来看postgresql中如何进行分裂，以及进行了那些地方的优化；
按分裂的节点类型，分为根节点，页子节点，中间branch节点的分裂；
根页面的分裂
在一开始，数据不多时，根页面节点就足够存下了，此时根节点也是叶子节点；随着数据的增多，根节点就需要分裂了。
它的分裂不同于其它类型，下面图示分析：
当root节点分裂时：
1.节点分裂
- 先加锁待分裂的root节点；
- 在本地内存中生成一个left节点，将它的
btpo_flags设置为分裂中，并且插入highkey，也就是右节点的最小值； - 在索引文件中生成right节点，注意这里是直接在索引文件中增加一个节点，同时加互斥锁；设置right节点的前继为待分裂的root节点，后继为空，因为它是最右的节点；
- 将旧root中的数据根据划分位置，分别移动到左右两个节点中；并且将待插入值插入合适位置，因为是分裂，所以一定是有空闲空间的，所以在此处直接插入；
- 将left节点拷到待分裂节点中；这样，left，right节点都在索引文件中了；
- 将left,right页面标脏，同时更新待分裂节点的右节点的前继为right节点，并生成分裂的WAL；
- 解锁待分裂节点的右节点；
2.更新父节点
- 然后新创建一个root节点，将左右节点的信息插入新的root节点中；
- 将left节点的正在分裂标志取消；
- 新root节点页面标脏，以及生成新root页面修改的WAL；
- 解锁root,left,right节点；
在通过pginspect插件看时，就会发现root节点的pageno随着数据增加会一直变动，其实就是树的层次在增加，每增加一层级时，就会新创建一个root页面；
叶子页面分裂
页子节点页面的分裂，是最常见的一种，当然也经过了很多的优化，比如对于相同键值的数据；还有对于多版本跨节点存储时，会再插入一条索引项，还有对于NULL值的存储；
先来看一下叶子页面分裂的整体流程示意图：
叶子节点分裂如下：
1.节点分裂
- 加锁待分裂节点；
- 在本地内存中生成一个left节点，将它的
btpo_flags设置为分裂中，并且插入highkey，也就是右节点的最小值； - 在索引文件中生成right节点，注意这里是直接在索引文件中增加一个节点，同时加互斥锁；设置right节点的前继为待分裂的root节点，后继为空，因为它是最右的节点；
- 将旧root中的数据根据划分位置，分别移动到左右两个节点中；并且将待插入值插入合适位置，因为是分裂，所以一定是有空闲空间的，所以在此处直接插入；
- 将left节点拷到待分裂节点中；这样，left，right节点都在索引文件中了；
- 将left,right页面标脏，同时更新待分裂节点的右节点的前继为right节点，并生成分裂的WAL；
- 解锁待分裂节点的右节点；
2.更新父节点
- 加锁待分裂节点的父节点，然后解锁右节点；这一步解锁也很关键，优化了并发性能；
- 将右节点信息，也就是左节点的highkey值, 插入父节点中; 当然这一步可能会递归进行,因为父节点有可能还会进行分裂，直到root再次分裂，就会增加树的层次；
- 生成父节点变动的WAL；
- 解锁父节点，left节点；
branch页面分裂
branch节点，是一种btree中间层的节点类型，它们存储的都是下层索引节点的页面位置和对应页面上的最小值；只有叶子节点上才会存储数据页的信息；
branch节点的分裂，类似于叶子节点的分裂；
只是在更新父节点时，多了一步，将left节点的正在分裂标志取消，也就是对于中间层的分裂已经完成；
新索引项加入
如果不发生分裂，那么插入的流程如下：
- 找到索引插入位置；
- 索引项插入页面，并给当前页面置脏标记；
- 更新meta页的fastroot；如果树的某一层只有一个节点时，这个节点就是fastroot，记录到meta页面，下次遍历时，直接从fastroot开始扫描；
- 检查是否需要记录fastpath对应的块，也就是叶子节点最右节点；
索引页面插入
因为btree索引是一种有序的索引，也是存储有序的，所以增加一条索引项时，如果在插入位置没有空槽位，就需要将当前位置及后面的索引项，向后移一个槽位，再将新索引项插入；
并发控制
在整个插入过程中，查找过程，还有分裂时持有多个块的情况进行了优化；
主要通过以下措施：
扫描和插入时
这两个过程中，只会对当前页面加锁；
在索引扫描时，结束一个索引页面就会释放，再加下一个索引页面加锁，这样保持了很好的并发访问性能；
索引项只记录向下的关系，所以在扫描过程中，会记录父子关系的stack，这方便在分裂时，向上递归；
索引分裂
在分裂的时候，会加多个节点的锁，加锁原则是从左到右，避免死锁发生；
分裂时减少了加锁的节点数量，从叶子节点开始，叶子页面分裂时，会加左节点和右节点的锁；当更新父节点时，加锁父节点后，就释放了右节点的锁；整个过程中持有的锁，可能最多就是三个节点，当然还有短暂持有的锁，如meta节点，还有待分裂节点的右节点的锁，最多时会有四个节点；
fastpath
记录叶子层的rightmost，对于null直接插入还有批量顺序插入时，直接就可以从fastpath找到插入节点，也就是叶子节点的最右节点；如果不符合时，再遍历查找；
这里使用了条件锁，得不到时，也会进行遍历查找，增加并发访问性能；
fastroot
当树的某一层只有一个节点时，那这个节点就是fastroot，不用从root进行遍历，而从fastroot遍历就可以，加快速度；
对于异常的保护
因为索引页面不像数据页面是多版本机制，为了保持索引的存储精炼，而采用了原地更新，这就需要在更新时，如果服务异外宕机了，数据还能保持一致性和完整性；
在插入时的保护
如果没有发生页面分裂，在插入数据时发生了异常，此时是由WAL来恢复；WAL记录了插入的位置，以及原有数据位置的变化；
在分裂时的保护
首先在分裂时，开始只将右节点加入了索引文件，分裂节点的数据并没有发生变化；此时异常并不会影响；
接下来，分裂节点数据发生变化，此时它的flag还是正在分裂中，那么数据其实是完整的，分别在左右两个页面上，只是从父节上只能找到左节点，从左节点再顺序通过后继链表就可以找到右节点，这在前面btree索引查找时就分享过。
结尾
非常感谢大家的支持，在浏览的同时别忘了留下您宝贵的评论，如果觉得值得鼓励，请点赞，收藏，我会更加努力！
作者邮箱：study@senllang.onaliyun.***
如有错误或者疏漏欢迎指出，互相学习。
注：未经同意，不得转载！
