大云海山数据库(He3DB) 内核分析 - Btree索引篇前言提到索引大家都不陌生日常生活中也常用到索引比如查字典课本的目录等等都是利用了索引的思想来快速找到想要的内容数据库也是一样引入索引来提升数据库读的性能但是没有免费的午餐索引的引入在提升读性能的同时会牺牲掉一部分写的性能且需要占用一定的磁盘存储空间所以合理的使用索引非常重要。索引是每个数据库最基本也是常用的功能最近在学大云海山数据库He3DB的过程中花了点时间研究了一下数据库中索引的实现He3DB 所支持的索引种类有B-Tree索引hash索引GiST(Generalized Search Tree)索引GINGeneralized Inverted Index索引Brin索引SP-Gist索引。本文并不打算详细的介绍全部种类的索引会挑一个最常用的B-Tree索引来介绍它的实现套路。既然叫B-Tree索引自然和B-Tree结构是分不开的可以联想到磁盘上索引文件的数据组织形式是以B-Tree的结构组织但实际He3DB实现的工程中是以B-Tree的一种变形结构BTree的数据结构来存储数据的。说索引实现之前先来回顾一下BTree的结构特点B树的所有的键值都在叶子节点并且键值之间使用双向链表的方式连接B树叶子节点保存了指向实际数据的指针非叶子节点保存了子树节点的最小值指针并不指向数据实际存储位置B树每次查找过程都会经历从根到叶子节点的路径基本知识回顾完之后下面会从B-Tree索引的创建查找插入删除几个部分来揭秘He3DB的B-Tree索引实现这部分内容会涉及到比较多的代码分析。Btree索引的创建先说第一个部分索引的创建关系型的数据库创建索引的路子都是大同小异He3DB也不例外先构建索引相关信息处理元数据再创建索引文件最后导数据到索引文件。这部分内容直接看流程图就完事了一目了然。流程图虽直观但展示不出实现的细节下面分别介绍一下上述流程图中涉及到的几个具体的结构体**Page**页是在流程图的_bt_load函数中被首次构建page承担着存储实际索引元组的任务是索引文件的最小存储单元也就是说索引文件中实际存储的是一个个的pageBTree的每个节点也就是一个page结构这些page被人为组织成了BTree的结构He3DB默认的每个页大小(pagesize)是8k每个page中可以存储很多个索引元组(itup)这些itup被逐个顺序的安排在page中当一个page存满了8k的数据之后会再创建一个新的page之后所有的itup都往新的page中插入并将已经插满的page落盘。看一下He3DB的page结构示意图分析一下这张图展示的page结构这张page结构图包含了PageHeaderDatalinpNitemNspecial space 4个部分。PageHeaderData里面存储的就是当前page的布局信息包括上述4个部分的起止位置page的大小和版本还有标志位信息。linpN这部分存储的是索引元组在page内的实际位置的指针每一个linp指针指向一个对应item位置linp内存结构对应代码里的ItemId的结构。itemN这部分就是实际的索引元组也就是itup对应代码中的IndexTuple结构。SpecialSpace在每个page的最后位置这块空间存储了当前page的左右兄弟节点指针页面类型叶子根元页等页面在Btree中的层号等。BTPageState这个结构首次构建也是在_bt_load函数实际上_bt_load是先构建的BTPageState后构建的Page再将BTPageState中的btps_page指向新创建page其他字段的信息也一并获取由此可见BTPageState描述的就是当前正在操作的page至于btps_next指针是用来指向父节点的BTPageState结构这个指针在所有索引元组插入完成后调整BTree每一层的最右节点时用到后面再说具体用法。由以上分析可以看出当一个page填满之后只要再创建一个page结构同时将BTPageState里面原来的page信息更新成为新创建的就实现兄弟节点复用BTPageState结构所以BTree的每一层只会有一个BTPageState结构。BTWriteState用于记录索引写入过程中的总体状态整个索引创建的过程只产生一个BTWriteState结构。BTMetaPageData元页BTree树上的第一个节点但是确是在整个树构建完成后再构建的元页节点元页中保存了B-Tree的版本根节点根节点层号有效根节点有效根节点的层号等。重要结构介绍完了现在可以用一段文字描述一下整个B-Tree的构建过程了首先扫描原表将原表元组转为索引元组并对索引元组进行排序然后调用_bt_load函数逐个的从spool中获取排好序的索引元组并将其添加到当前页面当填满一个页面之后重新创建一个新的page作为它的右兄弟节点创建新page后立马做两件事情第一把填满的page中最后一个元组添加的新page中作为新page的firstkey第二把填满的page的linp0指向最后一个元组也就是填满页的highkey并清除掉原来指向最后一个元组的linpn。在创建右兄弟节点后还会判断是否有父节点如果没有则一并创建一个父节点和一个描述父节点的结构BTPageState并和子节点的BTPageState通过btps_next指针相关联还会将满页的最小元组插入到父节点中这一步作用就是将父节点和满页相链接父节点可通过这个最小元组指针找到子节点再将左右兄弟节点通过SpecialSpace结构中左右指针连接起来最后再将满页写入索引文件重复上述过程直到所有的元组全部添加完成最后调用_bt_uppershutdown函数做收尾工作该函数是在元组插入过程完成之后调用主要用来连接父节点和最右侧的节点这个连接过程也是使用BTPageState结构中保存的向上指针btps_next来完成的完成连接工作之后每个最右侧节点从firstkey到highkey的linp指针依次向左滑动一个元组的位置最后一个linpn同样不再使用做完滑动之后再创建一个元页并写入索引文件到此整个BTree索引就构建完成了。再梳理一下B-Tree构建的过程先填充page填满之后创建右兄弟节点和父节点连接父节点和满页节点连接左右兄弟节点满页写入磁盘填充新page重复上述过程直到所有元组填充完再连接每一层最右节点和父节点。Btree索引的扫描关于创建索引的过程就说这么多B-Tree构建详细过程有很多经典的图大家有兴趣可以网上找找这里不在多说下面讨论一下B-Tree索引的查询。 在He3DB中当一条sql语句的查询条件包含索引列优化器就会将索引的查找考虑在内一旦优化器最终选择了索引扫就会生成相关的物理算子来执行索引上的扫描过程比如 Index Scan/BitMap Index Scan等。由前面的索引创建过程可以联想到如果执行计划走索引扫那必然牵涉到从索引回原表取其他列数据的过程也就是说走索引的执行计划执行所需要的总时间是索引扫描的时间加上回表的时间如果要想这两个过程比直接扫描原表的快一定要有特殊缩短时间的方法才能达到效果对于B-Tree索引来说主要用到的是BTree的查找特性一有序二每次查找都是经历从根节点到叶子结点的过程利用二分法将查找的时间复杂度控制在logN这样从索引文件在logN的时间内找到满足条件的索引元组在用这些索引元组去原表文件取表元组则是有着对应的偏移量可根据偏移量直接拿到表的元组避免全表扫这样就可以大幅缩短整个查询的时间。下面从代码角度剖析一下IndexScan这个算子的执行过程。根据刚才分析BTree构建过程在插完所有的itup之后最后一步是写入元页元页中保存了整个树的根节点信息查找的时候就是从B树最上层的的元页开始先从元页中得到根节点fastroot在调用_bt_binsrch在根节点上找出满足扫描条件的孩子节点因为BTree会将所有的key值都存在叶子结点所以这一个过程会一直重复直到找出叶子结点为止由于每个叶子结点可能会存有很多的索引元组在找出的叶子结点上需要再次调用_bt_binsrch函数进一步找出满足条件的索引元组的offset在调用_bt_readpage根据offset在page中找到itup如此就得到了IndexScan算子回表需要用的tid下图展示了tid的内存定义结构可以看出来tid中详细记载了当前tid所指向的表元组在哪个block以及block内的偏移所以再打开原表文件的时候可以直接定位到要找的内容到此整个索引查找的过程基本就结束了。还有一个需要区别一下的就是IndexScan和BitMap Index Scan都是索引扫描算子他们的区别在于Index Scan一次只返回一个tid而BitMap Index Scan会将所有满足条件的tid封装成为一个bitmap一次性返回给执行器执行器再利用bitmap逐条的回表这个设计可以减少索引底层的函数调用次数提升性能。Btree索引的插入下面再说说B-Tree索引的插入插入相关的数据结构BTScanInsert结构保存了要插入元组对应生成的scankey等信息B-Tree查询时也用到这个结构。BTInsertStateData结构在整个插入阶段工作它包含了要插入了itupitup_key, 插入的buf等信息。一个有索引的表对其插入数据生成的执行计划中是会包含索引相关的维护操作对于B-Tree索引来说btinsert函数就是做插入维护B-Tree索引的这个函数会先将表元组转换成索引元组在将索引元组插入B-Tree上的相应位置。btinsert函数首先将原表元组生成要插入的索引元组itup再用itup生成BTScanInsert结构该结构包含了查找插入位置需要用的关键信息scankey插入过程同样会调用到_bt_search函数来找到itup对应的节点号然后构建BTInsertStateData结构后续在页面上找到应该插入的偏移位置拿到位置之后就可以直接将索引元组插入到对应的偏移位置即可这里会有两种情况一种是当前页面剩余的空间充足可以容纳要插入的itup直接将元组插进去就完成了索引插入的过程还一种情况是页面剩余空间不足以容纳itup此时会发生页面分裂。_bt_split函数是He3DB处理B-Tree页面分裂的主函数在索引插入数据的过程中一旦发生页面分裂就会调用到这个函数它的处理逻辑是首先计算出一个合适的分裂位置创建一个新的左节点和一个右节点从原页的firstkey遍历到highkey根据分裂的位置将原page中的itup分成两份分别放在左右节点中这个遍历过程包含了新插入的itup插入对应的节点再将左page的所有itup拷贝到原page中释放左page到此就得到了分裂后的两个节点_bt_split处理完成然后再将原page的highkey也就是分裂后右节点的firstkey插入到父节点中将右孩子与父节点相连并递归的判断是否父节点也要分裂重复上述过程直到所有分裂出来的右节点都完成和父节点的连接分裂过程处理就结束了。Btree索引的删除最后再来讨论一下B-Tree索引的删除先看个delete语句的执行计划上图中的执行计划在删除原表数据前会先扫描表上的索引得到tid在回原表上删除表元组实际上删除表元组的操作只是将对应的表元组标记为DEAD状态并未实际的从磁盘中物理删除此时在查这条数据时虽然数据还在但由于表元组已经被标记为DEAD状态所以对数据库来说这条记录是不可查的。而这条记录只有在最终对表做vacuum操作时才会从BTree对应的page上真正的删除掉。vacuum删除物理索引元组的过程在对一张表做vacuum时如果表上有索引在那么会对应的去每个索引上删除相应的索引元组He3DB B-Tree索引提供了一个批量删除的接口btbulkdelete该函数会遍历除了元页之外的B-Tree所有节点并找出每个节点内需要delete的itup调用_bt_delitems_vacuum函数从对应的page中删除所有要删除的itup完成磁盘空间释放。到此本文的正文内容就基本结束了下面做个总结。1. 基于Btree实现的索引适用于等值和范围查找尤其是范围查找由于左右节点可以直接相连使得范围查找不必再回溯到父节点上加快了查找的速度。2.Btree内部节点指向下一层节点的位置叶子节点指向实际存储数据的位置。3. Btree索引的并发扫描插入和锁控制相关进阶内容下次再说吧