OceanBase-从0到1数据库内核实战教程学习笔记---7.数据库索引结构

本文是有关数据库索引结构的介绍;主要内容包括以下几点;

B;Tree散列表LSM-TreeMiniOB B;Tree

1. B;Tree

B;Tree 是 B-Tree 的一种变体;B-Tree 全称 Balance Tree;平衡多路查找树;;它可以自动保持与数据文件大小相适应的索引层次;这样可以起到预读数据的效果;另外它能使每个存储空间保持在半满与全满之间;减少空间浪费;B;Tree 与 B-Tree 的主要差别在于中间的节点不存储有效数据;并且叶子节点间有连接关系;能够有效加速遍历查找。



因为 B;Tree 叶子节点之间是有链接的;所以对于范围查找是十分友好的;

B;Tree 的插入原则上是递归的;

首先设法在叶节点为新建找到空闲空间;如果有的话;就把键放在那里;如果没有的话;那把该叶节点分裂成两个;并且把其中的键分裂到这两个新节点中;使每个新结点有一半或刚好一般的键;某一层的节点分裂在上一层看来其实就是插入一个新的键指针对;因此可以在这一较高层次上递归的使用上述插入策略;

B;Tree 的删除分为两种情况;

B;Tree 在使用过程中存在很多问题;最典型的有以下两点;

数据量增长导致路径变长;磁盘的IO会增加;高速海量的数据操作时;节点分裂/合并的迭代;带来额外的开销。

2. 散列表

散列表;又称哈希表;当桶的数量非常多;并且数据分布非常均匀时;散列表的定位速度是非常快的;


当一个查找键为 k 的新纪录需要被插入时;

删除数据与插入类似;如下图删除 h©:

查询通常通过布隆过滤器来提速;过滤不需要用到的存储块;


前面介绍的都属于固定的散列表;还有一种动态的散列表;比如可扩展散列表;它可以以2的倍数增加;当有新的数据插入时;如果存储已满;桶的数量便会成倍增加;它可以一直驻留在内存中;

3. LSM-Tree

上篇文章我们也介绍了 LSM-Tree;它的核心思想就是将数据先保存在内存中;同时写 log 日志;达到一定阈值时触发 Compaction 操作;将数据合并到磁盘中。

下图是 LevelDB 的 LSM-Tree;它除了 L0 层以外;其他层的 SSTable 都是按照 row key 顺序排列的;另外还包括黄色部分的 Log 恢复日志;Manifest 原数据信息等。

LevelDB 的 Insert 操作如下图;它首先会写日志;然后将数据插入到 Memtable;当 Memtable 达到上限时;会冻结成为 Immutable Memtable;并声称一个新的 Memtable;然后在后台将 Immutable Memtable 转换成 SSTable;再从 L0 层触发 compaction 操作。


查询的话;LevelDB 为每个数据块都创建了一个布隆过滤器;数据的查询是从内存向下一步步查找;按照时间顺序排序取得最新的结果;

4. MiniOB B;Tree

MiniOB 中的 B;Tree 和上面介绍的基本是一致的;它存储的每个存储块就是一个 Page;每个 Page 是由 page_num/common header/左右节点/data 构成;叶节点存储的是 Key: 索引列;RID Value: RID

内部节点与叶节点有两点不同;一是它没有左右节点的 page num;另一个是它的 data value 存储的是 page num。

索引文件中包含索引文件头;其中包含很多信息;如下图;

下图是一个典型的 MiniOB 场景;查询时可以通过 indexfile 的 page0 进行索引;

插入的操作如下;分为 page 存在和不存在两种情况;需要分别对待处理;



删除操作上;也分为两种情况;如果删除完后可以合并则进行数据合并;如果不能合并可能会存在数据重分布操作;



相比之前介绍的 B;Tree;MiniOB 的实现更简单一些。

今天的内容大概就这些;

最后的最后;如果大家感兴趣;可以多关注和参与 OB 的活动;https://ask.oceanbase.com/t/topic/35601006。