开发者学堂课程【从0到1数据库内核实战教程：数据库索引结构】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/16138
数据库索引结构
内容介绍：
一、 B+Tree
二、 散列表
三、 LSM-Tree
四、 MiniOB B+Tree
介绍数据库所有结构的相关知识，主要的内容会包括，B+Tree 、散列表、LSM-Tree，3种数据结构的介绍，以及 MiniOB B+Tree 的一个实现介绍。
一、B+Tree
首先是B+Tree，B+Tree是B数的一种变体B数，可以理解为balance tree平衡多种查找数。作为上用系统中常使用的一种所用结构主要有两个特点，一个是能够将结点大小与存储介质的存储单元相对应，一方面使结点出度更大数的层次更小，另一方面也能起到阅读数据的效果。二是能够保证每个结点或者说存储快的空间保持在慢慢与全板之间，减少空间浪费添加数它与因数主要差别在于中间结点不存放以下数据，能够使得结点的冲动更大，并且越结点间有着链接关系，能够有效的加速便利查找。
接下来对B+TREE具体的细节展开介绍，为了对B+Tree有一个直观的印象，大家可以先看游戏表这张图B+Tree，它将数据组织成一个数的形状，每个结点是一个存储块，这棵树它是平衡的，也就是从树根到树叶的所有路径都一样长。对于每个B+Tree，都有一个参数n来决定B+Tree所有存储块的布局，每个存储块会存放最多整个成长结合加一个指针。我们通过以下几个规则来限制了接下来所介绍的B+Tree示例，其中的话一结点，它最后一个指针是指向下一个列结点，其余的指针指向有效记录。它并不适用于所有的不加数，只是为了方便我们的介绍。在示例中，是等于三的，也就是说，每个块它可以存放三个键以及四个指针。这是一个不代表通常情况的小数字。这两个图分别是几个图。
这两幅图分别是特殊它典型的叶结点与内部结点的形态结点。它不需要完全充满，但是叶结点至少要有两个键值对，而内部结点，它至少要有一个键和两个指针，一个是这个结点它的一个充满度的最小约束。
1、B+Tree查找
B+Tree它的查找是从根到叶的递归过程。如果我们处在某个内部结点或者根结点，则通过结点中的键范围来找到下一层的结点。如果我们处于叶结点的话，就在其中直接进行查找。如果第二个键它是查找键，则第二个指针可以让我们找到所需要的记录，以查找键。按日期为例的话，我们从根结点开始其中。我有一个键13，而K37，它是大于等于13的，因此从第二个指针向下继续查找，以此类推的话，最后会在页结点中找到记录。由于B+Tree它的页结点前后存在链接，它对于范围查找来说是非常友好的。我们以查询十到15范围的键为例，首先通过键等于左边键时进行查找，找到页结点后按顺序向后依次判断键是否位于范围内，然后将位于范围内的记录取出即可。
2、B+Tree 插入
接下来介绍毕加索插入，插入它在原则上是递归的，首先会设法在适当的页结点为新建，去找到一个空间空间。如果没有，会将页结点分裂，而某层它的分某层的一个分裂操作。它在上一层来说其实就意味着插入一个新的建筑队，因此会递归的使用上层的一个逻辑，当我们在分裂结点并在。并在一起附件点进行插入的时候需要小心的处理。
举例，像图中这个加数插入件40，根据前数的一个查找过程，我们会找到第五个页结点并进行插入。如果说这个时候页结点未满，那么直接插入介质堆到37和41之间在。事实上，该液体点已满，需要分列这个液结点分列的话，首先它是会创建一个新结点。在这个场景下，它是会在原结点中保留两个键值对，然后将其余的一个键值对和新差的这个键值对移动到新的结点。现在我们还必须去插入一个直向新液体，点指针到它上一次的结点，并且将这个指针与键次时去关联起来，因为键次时，它是能够通过新液体点所访问到的最小键，那么理论上，需要在这个负键点中增加键次时形成一个23、31、40和43的键序列。但是很不幸，这个负结点它也是慢的
因此我们将前两个键，也就是23、31保留在原负结点中后一个键，也就是43移动到新结点，而中间的那个键，40则移动到更上一层的负结点去，用来划分在这两个结点之间的查找。关于键40，为什么移动到上一层，可以结合刚才所讲的中间结点，它每个键指针对的具体含义我们可以提示一下，就是在这个结点中，43所指向的指针，它是表示小于43的一个数，它数据范围，那么在这里事实上就是不需要存储，这个键40。
3、B+Tree 删除
然后是B+Tree的删除与插入类似，如果找到页结点按并将键值针对去删除后结点，它仍然满足充满距离的最小约束，那么不需要进行额外处理。但反之，需要为这个结点做以下两件事情，一个是从兄弟结点借鉴所实现的一个结点重构，一个就是与兄弟结点，完成的两个结点之间的合并。这两件事情，它都需要对附件点进行修改并且合并操作，它还会导致附件点的一个删除，从可能向上的递归使用同样的逻辑。让我们再从这棵、这棵树开始。
假设需要删除键七，这个键位于第二页结点，将其键值对以及质量的进度删除，此时结点只剩下一个键，然后要求每个叶结点至少有两个键，因此，会从左胸进去迁移过来一个键值对，并将负结点的键从七改为五，下一步在这个基础上再删删除键11，这个删除它同样是对第二页结点产生影响，但这一次，不能再从第一个键第一个结点去借鉴了，因为后面它的键数达到了最小值。另外，它的右边也没有兄弟，因此我们需要将这两个结点进行合并，合并成一个新的结点
合并后，我们继续去调整负结点。具体来说，它的两个指针被替换成了一个指针，并且原来的任务也不再有用，被删除了。此时该附结点会从右兄弟去借取一个指针，也就是一个原来的这个指向点，指向这个页结点的一个指针。 
然后并且这个指针的键，这是对应的这个键改为13，而这个键指三，它原来是位于根结点的，并且表示，通过这个被转移的指针所能访问的一个最小键。因此这个根结点这个键也需要修改，需要修改为23，也就是说通过这个第二个根结点，第二个这个指结点所能访问到的变结点的最小键，现在是从原来13变为23。所以根结点它其中的这个键也是需要更改的，这个过程相对来说是比较复杂的，而在插入和删除中，这些特殊的复杂的操作，它本质上其实都是为了保证比加数去始终维持在平衡的状态，进而去保持整棵树的一个性能稳定性。
4、B+Tree 主要问题
B+Tree它存在的主要问题，这里提两点，一是随着数据量的增长，数的层数增加，一结点访问的路径变长，使它的IO数会增加。但是这通常是发生在数据量非常大的情况，因为一般来说，每个存数块的大小，它其实是和存数单元保持一致的，而这个大小相对来说已经足够大了，因此，在通常情况数的层数都是不会很高的，而每增加一层，数据量其实是成指数级的一个增长。另一个就是在高速海量的数据更新下，B+Tree，它容易发生结点内频繁的分裂与合并，也就是刚才讲到的一些特殊的操作，这种行为它会在数的多层之间迭代传递，从而其带来一个开销。
二、散列表
接下来介绍散列表，又称哈希表，这种结构中它有一个散列函数H，是用来为以查找键为参数去计算，这个介于零到B减一的整数，其中B的话，它指统的数目桶的话，这里介绍统数组的概念，统数组就是表示，一个序号从零到B减一的数组，其中包含了B个数据集合，每个集合就对于数组中的一个统，如果说记录的查找键为K，那么我们会通过该记录映射到HK的桶中来，然后进行存储。比如说HK等于二，我们会在这个桶中进行数据的存储，当桶的数量足够多，并且数据分散足够均匀的时候，散列表的定位速度是非常快的，再常数级别。
在主存中，桶数组通常是由指向列表头的指针组成的，每个数据集合的话都由列表去构成。而在记录更多的一个数存中统数组通常是有一个或者多个存储块构成多个存储块，它可以通过存储一个附加的信息来进行链接，或者说我们直接将存储块数据存放，通过存储块号取余来划分同一个桶中的多个存储块。比如说，以B等于四为例，这里第五个存储桶就可以作为第零号桶的第二个存储块，五个存储块。
1、散列表的插入
当一个查找键为K的新记录，它需要被插入的时候，首先是计算HK，如果桶号为HK的空间的桶还有空间，就把该记录存放在该桶的存储块上。比如这种情况，或者把它存储在多个存储块中上有空间的那个存储块中，比如HK等于一的情况，如果这个桶没有空间，那么会增加一个新的桶，并将该桶链接到，并将存储块链接到该桶的最后一个存储块上，然后将记录去存入该块比如和HK等于三的这种情况。
2、散列表的删除
删除记录与插入记录的方式是类似的。当查找键为C的记录，需要被删除的时候，首先会找到同号为XC的同，然后从中去索取这个查找键的C的记录删除。如果能够去将记录在快捷键进行移动的话，那么删除记录后，这里其实可以选择把这两个块进行合并。由于记录的一个无序性反列表，它通常无法支持范围查询，常见的做法是使用混合的索引结构或者多个索引结构来特别支持范围查询。
3、辅助散列表的问题
弹力表在理想情况下是有足够多的桶，然后绝大多数桶它都只有三个块构成，这样一般查询只需要一次的次方腰。但如如果记落数不断的增长，最终就会出现一个桶由使用存储块构成的一个情况。因此的话，必须设法减少每个桶的块数，比如，通过减少哈希冲突来减少每个存储块的一个记录。进而去间接的减少每个图的快速，但是更有效的方法其实是减少无效的访盘，也就是这个图中对第一和第二个存储块的一个访问。
4、布隆过滤器
关于这一点，目前常见的解决方案是比如布隆过滤器，这里简单介绍一下它的原理，布隆过滤器是由一个固定大小的二进制向量，或者位图和多个异常元素组成的处理状态下，它的所有位都为零。当元素加入集合的时候，通过K的映射元素将这这个元素去映射到位数组中的K为零，然后并把它们置为一。这里，以三个因式元素为例，那么在查询某个元素的时候，只需要查看这些映射位是否都为零，就可以了。如果任意一个为零，那么被查询的元素是一定不存在的，如果都为零的话，则表示可能存在，那不如过滤器去运用在它系统的存储块中，能够在查询时取过滤元素存在的储存块。当然这是存在误误判的，当然误判是指如果存在的话，就是可能存在是这样的误判。更多细节的话，感兴趣的同学可以去咨询了解。
5、动态散列表
刚才讲到的散列表都是静态散列表，因为统的数目B从来不改变。但事实上散列表中还有一些动态散列表，它们允许B进行改变，并且通过B的增长是从侧面是可以减少每个图中的块数的。
这里简单介绍一种动态的散列表，可扩大散列表，它使用指向快的指针指针数组来表示统与主存的那个散列表类似指针数组，它是能够增长的，长度总是二点，幂数组每增长一次统的数目的翻倍。在某些情况下，它多么同是可以共享一个数的块。强烈函数H位一个键去计算，一个计算得到一个K位的二进制序列统的数目。使用二的I次幂表示。其中I它是指这个二进制序列的从第一、第一位，或者从最后一位开始算起的排位。这样说可能不太好理解。我们简单例子来进行介绍，我们假设K等于四，当前I等于一，那么此时同数组就只有两项，也就二加一次方分别对应零一，那么两个。这两个桶分别就是存储键被散列成以零和以一开头的201序列的记录。可以注意到每个存储块它其实存储的一个数字，这个是表示由散列函数得到的201序列中，它有多少位是用来确定记录在该块的一个成员资格。当向这个反列表中插入一个反列值为1010的序列时，因为它的第一位，是一所以该块，那这个记录它是属于第二块的，但是这个块它此时已经满了，你只需要分列，那么会去判断当前这个块的数字，它的一是与二相等的，那么所需要的分列就是将土数组进行一个翻倍，从而变成一个二等于二的情况。当我们再向其中分别插入散列值为0000和0111的记录的时候，因为这两个记录，它都属于第一个存的块。那么这个存储块可以出此时数字一，它是小于I的，那么就不需要再调整同数组，而是只需要将块进行分裂。我这里这里少少了一条箭头，大家可以注意一下这个零一会指向这个存储块，然后最后，如果插入一个散列值为1000的记录，以相同的逻辑散列表会扩展成这个样子。可末的散列表，它有一个明显的好处，就是我们查找一个记录的时候，它总是只需要查到一个数据块，并且统数组，它这个统数组通常是可以一直处留在内储存的。然后经过这个简单介绍，其实可以思考一下，可末的散列表的一个缺点。
三、LSM-Tree
接下来是SMG，它的全称是日志结构和命数，也就是log-Structured Merge Tree核心思想是将对数据的修改增量保持在内存中，达到指定的大小限制后，将这些修改取批量的顺序写入磁盘，从而达到最优的写性能。 LSM的基本结构如图所示，数据被放进了多层。其中的话，C0是存储在内存的，其他层存储在外层，数据在每一层按照K的大小依次排列，并且这些层的容量依次是成倍、成成倍的增加。当建筑队写入SMG时，首先会被插入到位于内存的C0，当C0满了以后，C0的数据会与C1的数据进行合并。合并后的结果会重新写入C一同理当ci满了的时候，Ci也会与ci加一合并，合并后的结果写入ci加一是合并操作，被统称为competition操作，而在查找指定键的时候，我们需要。也就是从C0逐层向下进行查找，可能会需要便利多层才能找到，这只是SMG的一个基本概念。在实际应用的时候，我会考虑到非常多的问题。为了对它有一个更直观的理解，我们以常见的LevelDB的SM趋势线来加深印象。
1、LevelDB 
两个DB的SM去实现是这个样子，它主要有两部分组成，一部分是驻留在内存的Memtable和Memtable，也就是内存表和只读内存表对应着前面讲的C0，另一部分存储在外存，并且分成了多层，从L0开始，分别对应前面讲到的C1和到到CM，另一部分。然后其中的话，它每层是由多个顺序字符串表，也就是SSTable文件来组成的。KVKL的有效数据就被东方，在这些SSTable文件中，除了L0层的话，其他层它存放的SSTable都是按key的顺序排列的。也就是说，这些除了要连存以外的SSTablee文件的问题，它的范围是没有重叠的。除了数据外，LevelDB它还有着存储最近数据更新，已经做故障恢复的一个log文件，存储当前数据库源数据，比如每层包含有哪些table文件，每个文件整体的范围，以及其他人数对现实的manifest文件，还有就是记录当前所使用的文件的carry文件。
LDB的数据写入流程可以分为简单理解，可以是两步，一个就是首先追加一条日志记录到log文件中，然后将数据去写入到MemTable，就这样一个写入操作其实已经完成了。其中的话，SSTable它实现为跳表，，它的功能和平衡数值是类似的，但是实现上更为简单并且维持平衡的操作。并在前面当SSTable的容量达到上限的时候，它会转变成一个Im not for man table只允许读不允许写，并且创建一个新的MemTable共写入Im mutable MenTable，它未来会转换成SSTable文件，这是一个后台的一个操作，并且去直接下调到L0层。因此的话，L0层，它的SSTTable文件之间是可能存在数据重叠的。这是最后的重叠的，而随着main table不断的被转化成SSTable文件并写入L0后，L0的文件数量会超过容量的限制，进而触发compacition操作。
2、Compaction
以图为例，由于L0它。那么由于L0它的文件存在范畴里，会从L0读取所有文件，然后在L0的下一层，也就是L1找到K范围与L0所读取文件有重叠的所有文件，初衷是这两个文件，然后将这些文件在内存读取到内存并进行一个合并排序后重新生成新的LM文件，并写入L1，最后将会变成。这样的一个形态，这L0中的文件相当于和L1合并成了这四个文件，其他层的合并，它也是类似的，只是说每次它只是从当前层选取一个SSTable文件与下层进行合并。Compete操作，它是FNG内部数据整合的一个机制，也是其中最复杂的过程，具体实现起来是有很多细节与优化手段的。
3、Seek
对于查询来说，首先是在Memtable和Immutabl 中查询，如果说都没有查到，则在外存中继查找。在外存中查找时，会从manifest文件中读取各层中ex table文件的K范围，然后找出可能包含查询K的SSTable文件，这个信息它一般是会缓存在内存中的，除了L0层以外，其他层它最多是只有一个SSTable文件可能包含查询键，随后，会将这些文件按照所在的层次进行排序，位于L0层的在前，然后L0层的文件则按照时间的先后顺序逆序排列。最后，按照顺序依次在s table文件中进行查找。像SSTable文件中，它的数据是排序的，并且是按照多个数据块进行切分，在内部有所有信息去记录各个数据块中K的范围，因此查询一般首先通过所有信息去确定可能包含P的数据块，然后在数据块内查找。还记得之前讲到的不容过滤器吗？在这里levelDB，它其实在每个SSTable文件中都为每个数据块建立了一个不能过滤器，在数据块内的查找是可以首先通过不能过滤器来进行提前检验的。如果说确定是不存在，那么会再到下一个这个文件后面看到
4、Leaf Page
最后，来介绍MiniOB B+Tree的时间在基本的逻辑上B+Tree和之前介绍的B+Tree其实是一致的。可以回想一下刚才所介绍的内容，比欧比中B+Tree，每个结点所对应的存数块，它就是一个配置，每个配置首先是有一个配置序号，这个配置number，然后紧跟着一个common header，包括了它是否为叶结点，结点中Key个数，父结点的一个page num，然后此外的话叶结点也是this page。它还保存了左结点的一个page num和右点的一个page num，这是用来遍历的。然后配题，最后剩下的空间就是去存放。其实对变结点，它所存放的键是所以列的值加上ID值，其中ID，它是表示该行数据在磁盘上的一个位置。有效的键值数据，它都是存放在叶结点上的，和之前所介绍的必加速度叶结点内的值是直线指记录的一个指针是有所不同的。
5、Internal Page
A部结点的话与a结点有两种不同，一个它没有所用间接的，第一个，第一个是间接对称中存储的值是最近的，一个是标识直接点的一个定位位置，以图为B的话，键值对在本层的一个最左侧的一个结点，是这样存放的，第一个键值对中的键，它是无效的，不会用于比价。而在其余的内部结点，因为可以理解一下其余的内部结点，其实最开始是从最左侧结点所分裂而来的，那么它建的对，就是这样一个存段形式，因为如果比如这个结点慢慢的分裂，那么第一次分裂的时候从中间。先切成两半，切出来的右半部分就会是这样的一个形式。
四、MiniOB B+Tree
所有的结点，也就是配置，它都是存储在外存的所有文件index盖中，其中文件的第一个配置就是所有文件头存储的一些原数据，比如说配置的page num，内部结点和叶子结点能够存储的键值，这个最大个数。
1、B+Tree
然后这个是一个简单的MiniOB B+Tree的示例，其中的话页结点，它是能够访问到左右收益的，并且这也不能叫左右收益，就是左右结点，并且每个结点它都是能够访问到负结点的。那B+Tree的设定其中，液结点它是能够访问到左右兄弟的，并且这也不能叫左右兄弟，是左右结点，并且每个结点它都是能够访问到父结点的。查询的时候我们会从 page开始，逐层向下定位到目标叶结点，在每个配置内是电力搜索查找键，如的page，我们能够从index file的第一个配置配定点中得到。
2、Insert（split）
在插入的时候我们会首先定位到叶结点。比如图中的配角，然后在结点内定位一个插入位置，如果结点未满，我们会将建立一个插入指定位置，并向后移动部分数据。而如果结点已满，那么我们需要对进行分列。我们首先创建一个右分的结点。比如说配置五，然后在原结点保留前一半的键值对，剩余的键值对则移动到新点，然后根据之前定位的插入位置，判断是插入到page2还是page 5。由于我们新这个结点。
需要在附结点中插入一个新键值对，对这一步涉及到原子点新结点，以及新结点中的最小键。分为两种情况，第一种情况是有附结点，一个是刚才介绍的这种图中的情况，那么，直接将新结点的那组的最小键以及新结点的page num作为键值对插入附结点即可
第二种情况是没有分结点，那么会创建一个新的根结点把。除了把新结点的一个键值的插入，还会把原结点的配置num作为第一个键值对的值进行插入。如果负结点的键值的插入同样触发了分类操作，那么会按照上述的步骤进行递归执行。
3、Dele（coalesce）
删除时，会首先在结点里删除你的键的对，然后判断其中键的对数目是否小于一半。如果是，需要进行特殊处理，比如在配件中删除一个键的对，导致其键的对数量小于一半，此时会通过它的附近点去找到该兄弟的左兄弟。该结点的左兄弟，如果是最左边的结点的话，就找他的右兄弟，因为他没有做兄弟。如果两个结点的所有键值对能够容纳在一个结点里，那么进行合并操作，将右结点的数据迁移到左结点并删除，附结点中指向右结点的键值对即可。
如果两个结点的所有键值对不能容纳在一个结点里的进行重构操作。当删除建筑队的结点，它不是第一个结点的时候，比如是配置，那么，选择将左结点左松地队最后的这个队移动到的当前的这个配置并修改副结点中指向当前结点的键就是这种形态。而如果当前结点，也就是删除键值对的结点是第一个配第一个结点的时候，会选择将右兄弟的第一个键值对去移动到当前结点中父结点，中指向右手这个键，
上述这两种操作中合并操作，它会导致负结点射出键值对，因此是可能向上递归的去进行合并的重构的。相比于最开始介绍的倍加数，MiNiOB倍加数，其实是更简单的一种实现方式。因为是在多层的中间，极点中其实是存储了冗余的键，这样就简化了分列和合并时所所需要的考虑到的一些处理状况，可以思考一下这个问题。
