置信你对数据的索引并不生疏，最常见的索引构造是 B+Tree，索引能够放慢数据库的检索速度，能极大地缩小存储引擎须要扫描的数据量。然而你晓得为什么用了索引之后，查问就会变快？B+ Tree 的构造原理是什么？8 月 25 日 19:30 实战教程第三期 OceanBase 社区将率领你学习数据库索引构造，从根底的数据结构常识介绍，到 MiniOB 我的项目索引构造的实现，带你深刻了解数据库是以什么样的形式放慢对数据的检索。
除此之外，本期课程还将持续学习 OceanBase 存储引擎构造，带你理解 OceanBase 的数据分层构造和存储格局、以及数据在 OceanBase 中从插入到查问的整个过程，加深对 OceanBase 存储构造的了解。
本期能帮你解决什么问题？
1、为什么大部分的数据库存储引擎都抉择应用 B+Tree 索引构造？
2、以 OceanBase 为例，深刻学习一条数据从写入到查出在数据库中的的执行流程。
3、练习题没思路？OceanBase 技术专家在线为你解析 MiniOB Drop Table 实现思路。
直播内容抢“鲜”知
MiniOB B+Tree 实现
在根本的逻辑上，MiniOB B+Tree 和 B+Tree 是统一的，查问和插入都是从根逐层定位到叶结点，而后在叶结点内获取或者插入，插入过程导致叶结点满的话同样会决裂，并向上递归这一过程。
每个结点组织成一个固定大小的 page，每个 page 首先有一个 page_num 示意 page 在文件中的序号，而后每个结点 page 都有一个 common header，实现为 IndexNode 构造，包含 is_leaf（是否为叶结点），key_num（结点中 key 的个数），parent（结点父结点的 page num），当 parent=-1 时示意该结点没有父结点。除此之外，Leaf page 还有 prev_brother（左结点的 page num）和 next_brother（右结点的 page num），这两项用于帮忙遍历。最初 page 所剩下的空间就程序寄存键值对，叶结点所寄存的键是索引列的值加上 RID，RID 是该行数据在磁盘上的地位，值则是 RID。也就是说无效键值数据都是间接寄存在叶结点上的。
外部结点和叶结点有两点不同，一个是没有左右结点的 page num，另一个是所寄存的值是 page num，即标识了子结点的 page 地位。键值对在外部结点有如上图的两种组织模式，每一层最右边结点的第一个键值对中没有存储键。
所有的结点，即 page 都存储在外存的索引文件 IndexFile 中，其中文件的第一个 page 是索引文件头，存储了一些元数据，如 root page 的 page num、外部结点和叶子结点可能存储键值对的最大个数等。
一个简略的 MiniOB B+Tree 将如上图所示，其中叶结点可能拜访到左右叶结点，并且每个结点都可能拜访到父结点。咱们可能从 IndexFile 的第一个 page 失去 root page，而在晓得一棵 B+Tree 的 root page 当前就可能拜访到任意一个结点了。查问时咱们会从 root page 开始逐层向下定位到指标叶结点，在每个 page 内遍历搜寻查找键。
在插入时，咱们首先定位到叶结点，如图中的 page2，而后在结点内定位一个插入地位，如果结点未满那么将键值对插入指定地位并向后挪动局部数据即可。而如果结点已满，那么须要对其进行决裂，咱们将先创立一个新的右兄弟结点，即 page5，而后在原结点内保留前一半的键值对，残余的键值对则挪动到新结点，并批改 page2 的后向 page num，page5 的前后向 page num 以及 page4 的前向 page num，再依据之前定位的插入地位判断是插入 page2 还是 page5，并实现叶结点的插入。此外，因为咱们新增了结点，咱们须要在父结点也插入新的键值对，这一步将波及到原结点，新结点以及新结点中的最小键，分为两种状况：
1、有父结点，那么间接将新结点中的最小键以及新结点的 page num 作为键值对插入父结点即可。
2、假如此时没有父结点，那么咱们将创立一个新的根结点，除了把新结点键值对插入，还会将原结点的 page num 作为第一个键值对的值进行插入。
如果父结点的键值对插入同样触发了决裂，咱们将按上述的步骤递归执行。
失常的删除操作咱们就不再介绍，这里咱们介绍一下一些波及结点合并的非凡状况。
删除时咱们会首先在结点内删除键值对，而后判断其中的键值对数目是否小于一半，如果是则须要进行非凡解决。这里咱们不特指叶结点，而形容一种普适的状况。
首先咱们通过父结点找到该结点的左兄弟，如果是最右边的结点，则找到其右兄弟。
如果两个结点的所有键值对能包容在一个结点内，那么进行合并操作，将右结点的数据迁徙到左结点，并删除父结点中指向右结点的键值对。
如果两个结点的所有键值对不能包容在一个结点内，那么进行重构操作，当所删除键值对的以后结点不是第一个结点时，咱们抉择将左兄弟的最初一个键值对挪动到以后结点，并批改父结点中指向以后结点的键，而在以后结点是第一个结点时，咱们抉择将右兄弟的第一个键值对挪动到以后结点。
在上述两种操作中，合并操作会导致父结点删除键值对，因而会向上递归地去判断是否须要再次的合并与重构。
存储格局概述
存储分层构造
在 OceanBase 数据库的存储视角看，存储构造里最上层是 Partition Group，对应一个分区组，很多时候咱们也将其简称为 PG。同一个 PG 中的多个 Partition 始终绑定在一起，那么对于同一个 PG 的事务操作就会被优化为单机事务，写入性能会更好。每个 Partition 蕴含与之对应的多个版本的 Table Store，每个 Table Store 蕴含特定工夫数据快照 sstable。当历史版本的 Table Store 没有被拜访时，会通过 GC 线程回收掉。
Table Store 外部，数据依照热、温、冷的程序，顺次散布在 MemTable、Mini/Minor SSTable、Major SSTable 中。最新数据写入 Active MemTable，当 MemTable 达到肯定大小后，会解冻不再写入，创立新的写入 MemTable。为了节俭内存，解冻 MemTable 会转储写到磁盘文件上，生成 Mini SSTable。当 Mini SSTable 个数增多时，各个 SSTable 间主键穿插的概率会增大，影响查问效率，这时会触发 Mini/Minor SSTable 之间的合并，将多个多版本 SSTable 合 并成 Minor SSTable。
OceanBase 采纳 LSM Tree 的数据组织模式，数据只能以追加的形式写入。每次插入、更新、删除都是一条写入记录，MemTable 和 Mini/Minor SSTable 保留了数据的多版本信息，蕴含比拟多的冗余信息。而事实业务中，个别比拟少更新历史数据，并且只须要读取数据的最新版本，这样对于历史冷数据存储，有比拟多的优化计划。OceanBase 零碎运行时，在满足肯定条件时，会选取某个历史快照点，读取数据最新版本，写入 Major SSTable 中。Major SSTable 只保留主键在快照中的最新残缺行，采纳了行列混存的模式，对数据进行分段编码和压缩，缩小数据存储老本的同时极大地提高了查问性能。
内存数据格式
OceanBase 数据库的内存存储引擎 MemTable 由 BTree 和 Hashtable 组成，在 HashTable 和 BTree 中存储的均为指向对应数据的指针。
Hash Table 比拟适宜按主键查找，实用于 dml 时主键校验或者其它按主键查找；BTree 中数据都是按主键有序的，比拟适宜按主键范畴查找。
磁盘文件格式
OceanBase 的磁盘存储文件叫作 SSTable，分为多版本 SSTable 和基线 SSTable。Mini SSTable 和 Minor SSTable 都是多版本 SSTable，它蕴含一段间断工夫内写入的数据；Major SSTable 是基线 SSTable，它蕴含某个快照点内的所有残缺提交数据。为了兼顾写和读的性能，SSTable 外部又按数据大小分为宏块和微块。宏块是数据写 IO 的根本单位，大小为 2M 定长数据块；微块是数据读 IO 的根本单位，为变长数据块，微块外部数据能够依照行存或者列式编码存储，每个宏块蕴含多个微块，如下图所示。
在宏块的最后面的是宏块头，记录宏块外部微块个数，微块数据起始地位等信息；前面跟着的就是一个个长度不固定的微块，存储用户数据；在微块之后，存储微块索引信息(Micro Block Index)，记录每个微块在宏块内的绝对偏移 Offset、每个微块的 EndRowKey 等信息。
更多具体内容，敬请关注 8 月 25 日 19:30「从 0 到 1 数据库内核实战教程」官网课程。
附录：
内核实战教程第一期 | 成为内核开发者的第一步：搭建研发环境
内核实战教程第二期|带你揭开数据库存储构造的神秘面纱
课程回放
赶快扫描下方二维码进入「OceanBase 入门到实战」群
关注课程动静，和更多小伙伴一起学习提高
为帮忙大家更好的学习数据库常识，结交新的敌人
将来 OceanBase Meetup 也会走到更多的城市中
大家进群后批改本人的群昵称哦【格局：姓名 - 城市 - 职位】