博客

1 主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。上图展示了一个4 x 4的主存模型。

1.1 主存的存取过程

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

2 磁盘存取原理

与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

磁盘读写时涉及到磁盘上数据查找，地址一般由柱面号、盘面号和块号三者构成。也就是说移动臂先根据柱面号移动到指定柱面，然后根据盘面号确定盘面的磁道，最后根据块号将指定的磁道段移动到磁头下，便可开始读写。

整个过程主要有三部分时间消耗，查找时间(seek time) +等待时间(latency time)+传输时间(transmission time) 。分别表示定位柱面的耗时、将块号指定磁道段移到磁头的耗时、将数据传到内存的耗时。整个磁盘IO最耗时的地方在查找时间，所以减少查找时间能大幅提升性能。

下图是磁盘的整体结构示意图。

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

下图是磁盘结构的示意图：

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

2.1 局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

3 数据存储

3.1 顺序存储

顺序存储是一个让人又爱又恨的玩意儿。爱是因为它理解起来比较简单，查找起来也比较方便；恨是因为这玩意儿太傻瓜，它只一次性地问内存要一段连续的空间，而且坚决不管在实际应用中够用不够用，而且这货在插入和删除元素时居然需要O(n^2)的时间复杂度，这个让人有点无语。那二叉树的顺序存储怎么样呢？让我们来分析分析。

比如说我有一棵完全二叉树，如图1(a)所示。该二叉树中有6个元素，可以将这六个元素按照层次从上到下，每一层从左到右的规则依次放入一个数组中，如图1(b)所示。除了数组的内存空间的问题外，这个看起来还过得去。但是，悲剧就要来了。



比如说，我有一棵一般二叉树，这棵二叉树只有四个结点（A/B/C/D），A拥有左右子树B/C，B是光棍没有孩子，C计划生育贯彻得好，仅有一个孩子D。但是为了能够方便地从双亲找到孩子（或者从孩子找到双亲），需要构建一些“虚结点”，从而使得一般二叉树“虚化”为完全二叉树，如图2(a)所示，B的两个孩子就是虚结点。然后按照完全二叉树的顺序存储方式进行存储，存储结果如图2(b)所示，数组中脚标为3的位置存放B的左子树，由于是虚结点，所以为空；脚标为4的位置存放B的右子树，同样因为是虚结点，所以为空。可以看出，对于一般二叉树，如果虚结点过多的话，数组中会有很多的空值，贼浪费空间。当然，如果您还觉得这样能过得去的话，让我们看看下面的退化二叉树吧，纯属洗脑了。



现在来演示一下万恶的退化二叉树，如图3(a)所示，该二叉树深度为3，但是恶心的地方到了，总共的元素个数也为3，这样，如果按照2中的方式顺序存储的话，数组中势必会有更多的元素为空。随着二叉树层数的增多，空元素是以指数级在增长的。如果这样的话，该会浪费多少内存空间啊，太可怕了。



当然，没有解决不了的问题，链式存储就是解决该问题的神器！

3.2 二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

3.2.1 查找过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

3.3 链式存储

链式存储的结构分为两种：二叉链表结构和三叉链表结构。

3.3.1 二叉链表结构

一个二叉链表结点由三部分组成：数据域，左孩子指针和右孩子指针，如下图所示。

其中，数据域data用来存放结点信息，左孩子指针lchild用来指向该结点的左子树，右孩子指针rchild用来指向该结点的右子树。图4(a)所示的完全二叉树的二叉链表结构如图4(b)所示。

3.3.2 三叉链表结构

三叉链表结点是在二叉链表结点的基础上，增加了一个指向双亲结点的指针域，如下图所示。

其中，data表示二叉树结点的数据域内容，lchild指向该结点的左孩子，rchild指向该结点的右孩子，parent指向该结点的双亲结点。图5(a)所示的完全二叉树的三叉链表结构如图5(b)所示。

3.4 顺序存储与链式存储比较

1. 顺序存储分配的内存空间大小是固定的（文件系统随着增加、删除操作的进行，在存储空间上就会产生大大小小的碎片），不好根据二叉树结点数目的增多而动态扩展。如果内存空间分配过大，势必造成内存空间的浪费；如果分配过小，则会产生数组溢出的问题。另外，顺序存储在增加和删除结点时时间复杂度为O(n^2)。顺序存储的好处是方便查找结点。
   
   优点：存取速度高效，通过下标来直接存储。
   
   缺点：插入和删除比较慢，不可以增长长度。
   
   比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序。
2. 链式存储可以动态分配内存空间，比顺序存储更加灵活、方便，结点的最大数目仅与系统存储空间相关。另外，在插入/删除结点时的时间复杂度仅为O(n)。因此，在对二叉树操作时更多采用链式存储结构。
   
   优点：插入和删除速度快，保留原有的物理顺序，比如：插入或者删除一个元素时，只需要改变指针指向即可。
   
   缺点：查找速度慢，因为查找时，需要循环链表访问。

3.5 二叉链表与三叉链表

三叉链表结点比二叉链表结点多了一个指向双亲结点的指针，因此增加了空间开销。但是，三叉链表的好处是既可以查找孩子结点，也可以查找双亲结点，在需要频繁查找双亲结点的应用中更为方便。

4 直接寻址表

4.1 概述

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假如某应用要用到一个动态集合，其中每个元素都有一个取自全域U={0,1,…,m-1}的关键字。同时假设没有两个元素具有相同的关键字。

用一个数组(即直接寻址表)T[0…m-1]表示动态集合，其中每个位置(或称槽或桶)对应全域U中的一个关键字。如下图所示说明了这个问题。槽K指向集合的一个关键字为k的元素。如果该集合没有关键字k的元素，则T【k】=NULL。

如此一来，就可以充分利用数组的定位性能进行数据定位。

4.2 缺点

直接寻址存在一个很明显的问题。如果域U很大，在一台典型计算机的可用容量的限制下，要在机器中存储大小为U的一张表T就有点不太实际，甚至不太可能。如果实际要存储的关键字集合K相对U来说很小，那么分配给T的大部分空间都要浪费掉。

5 散列表

散列表也称为哈希表，由直接寻址表改进而来。是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

在哈希方式下，该元素处于h(k)中，即利用哈希函数h,根据关键字k计算出槽的位置，函数h将关键字域U映射到哈希表T[0…m-1]的槽位中，如下图所示：



哈希表技术很好的解决了直接寻址遇到的问题。但是这样还是有个小问题。如下图所示两个关键字可能映射到同一个槽上。一般将这种情况称之为发生了碰撞。在数据库中一般采用最简单的碰撞解决技术，这种技术被称为链接法。

在链接法中，把散列到同一槽中的所有元素都放在一个链表中，如下图所示，槽j中有一个指针，它指向所有散列到j的元素构成链表的头。如果不存在这样的元素，那么j为NULL。

5.1 哈希函数

最后要考虑的是哈希函数，哈希函数h必须可以很好的散列，最好的情况是能避免碰撞发的发生。即使不能避免，也应该使碰撞在最小的情况下产生。一般来说，都将关键字转换成自然数，然后通过除法散列、乘法散列或全域散列来实现。数据库中一般采用除法散列的方法。

在哈希函数的除法散列算法中，通过取k除于m的余数，将关键字k映射到m个槽的某一个去，即哈希函数为：

h(k)=k mode m

5.2 优点

不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

5.3 缺点

它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

6 跳表

听到跳表（skiplist）这个名字，既然是list，那么应该跟链表有关。

跳表是有序链表，但是我们知道，即使对于排过序的链表，我们对于查找还是需要进行通过链表的指针进行遍历的，时间复杂度很高依然是O(n)，这个显然是不能接受的。是否可以像数组那样，通过二分法进行查找呢，但是由于在内存中的存储的不确定性，不能这做。

但是我们可以结合二分法的思想，没错，跳表就是链表与二分法的结合。

1.链表从头节点到尾节点都是有序的

2.可以进行跳跃查找（形如二分法），降低时间复杂度



一个有序的链表，我们选取它的一半的节点用来建索引，这样如果插入一个节点，我们比较的次数就减少了一半。这种做法，虽然增加了50%的空间，但是性能提高了一倍。如上图。

既然，我们已经提取了一层节点索引，那么，可以在第一层索引上再提取索引。如下图。



对于node5来说，它的next：

node5->next[2] = tailNode;
node5->next[1] = node7;
node5->next[0] = node6;

对于node7来说，它的next：

node7->next[1] = node9;
node7->next[0] = node8;

对于node3来说，它的next：

node3->next[0] = node4;

6.1 查找

如果我们要找node6节点，第一次比较headerNode->next[2]的值，也就是node5的值。显然node5小于node6（跳表的数据是有序的），所以，下一次应该从第2级的node5开始查询，也就是令targetNode = targetNode->next[2];

第二次应该比较node5->next[2]的值，也就是tailNode的值。tailNode的值是最大的。所以结果是大于，下一次应该从第1级的node5开始查询。这里从第2级跳到第1级。但是没有改变targetNode。

第三次我们应该比较node5->next[1]的值，也就是node7的值。因为node7大于node6，所以，下一次应该从第0级的node5开始查询。这里从第1级跳到第0级。也没有改变targetNode。

第四次应该比较node5->next[0]的值，也就是node6的值。这时终于相等，找到了，结束。

如果小于，targetNode往后移，改变targetNode = targetNode->next[0]，如果大于，则没找到，结束。因为这已经是第0级，没法再降了。

综上：

当targetNode->next[i]的值 < 待查找的值时，令targetNode = targetNode->next[i]，targetNode移到第i级的下一个结点；

当targetNode->next[i]的值 > 待查找的值时，向下降级，i- – ，不改变targetNode；

当targetNode->next[i]的值 = 待查找的值时，向下降级，i- – ，不改变targetNode。

最后，再次比较targetNode->next[0]和theElement，判断是否找到。

所以整个运算下来，targetNode是要查找的节点前面那个节点。

6.2 插入

当有2级索引时，新的节点先和2级索引比较，再和1级索引比较，最后和原链表比较，最终插到原链表中。当节点很多时，比较次数是原来的四分之一。

当然，当节点足够多的时候，我们还可以继续加索引，保证每一层索引数是低级索引的一半。当这一层只剩两个节点时，就没有必要再建索引了，因为一个节点没有比较的意义。

当很多节点插入时，上层索引节点已经不够用，我们需要在新节点中选取一部分节点提到上一层，跳表的设计者用“抛硬币”的方法选取节点是否提拔，也就是随机的方式，每个节点有50%概率会提拔。这样虽然不会让索引绝对均匀分布，但也会大体上是均匀的。

综上,插入的步骤：

1. 新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
2. 把索引插入到原链表。O（1）
3. 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
   
   总体上，跳表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。

6.3 删除

1. 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
2. 删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
   
   总体上，跳表删除操作的时间复杂度是O（N）。

6.4 应用

Redis当中的Sorted-set这种有序的集合，正是对于跳表的改进和应用。

相比于二叉查找树，跳表维持结构平衡的成本比较低，完全靠随机。而二叉查找树需要Rebalance来重新调整平衡的结构。

7 树

树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树：

7.1 树的定义

1. 树是元素的集合。
2. 该集合可以为空。这时树中没有元素，我们称树为空树 (empty tree)。
3. 如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与它的子树的根节点用一个边(edge)相连。

7.2 树的实现

树的示意图已经给出了树的一种内存实现方式: 每个节点储存元素和多个指向子节点的指针。然而，子节点数目是不确定的。一个父节点可能有大量的子节点，而另一个父节点可能只有一个子节点，而树的增删节点操作会让子节点的数目发生进一步的变化。这种不确定性就可能带来大量的内存相关操作，并且容易造成内存的浪费。

一种经典的实现方式如下:



拥有同一父节点的两个节点互为兄弟节点(sibling)。上图的实现方式中，每个节点包含有一个指针指向第一个子节点，并有另一个指针指向它的下一个兄弟节点。这样，我们就可以用统一的、确定的结构来表示每个节点。

8 二叉树

二叉树特点是每个结点最多只能有两棵子树，且有左右之分，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：



由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。

8.1 顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点。结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。



But，考虑一种极端的情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2的k次方-1个存储单元空间，这显然是对存储空间的浪费，所以，顺序存储结构一般只适用于完全二叉树。

8.2 链式存储结构

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

9 满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

10 完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。如下图所示：

11 二叉排序树

给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。



二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

11.1 查找

步骤：若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

11.2 插入算法

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

：新插入的结点总是叶子结点。

1.1. 删除结点

在二叉排序树删去一个结点，分三种情况讨论：

1. 若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
2. 若
   
   p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点
   
   f的左子树（当
   
   p是左子树）或右子树（当
   
   p是右子树）即可，作此修改也不破坏二叉排序树的特性。
3. 若
   
   p结点的左子树和右子树均不空。在删去
   
   p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令
   
   p的左子树为
   
   f的左/右(依
   
   p是
   
   f的左子树还是右子树而定)子树，
   
   s为
   
   p左子树的最右下的结点，而
   
   p的右子树为
   
   s的右子树；其二是令
   
   p的直接前驱（或直接后继）替代
   
   p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让
   
   f的左子树(如果有的话)成为
   
   p左子树的最左下结点(如果有的话)，再让
   
   f成为
   
   p的左右结点的父结点。

12 平衡树

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。

13 平衡二叉树

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

14 红黑树

红黑树也是二叉查找树，红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。

由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

15 平衡多路查找树

平衡二叉查找树的时间复杂度是O（logN），查找次数和比较次数较少，但是对于磁盘的IO次数，最坏情况下磁盘的IO次数由树的高度决定，所以减少磁盘IO次数就必须压缩树的高度，让瘦高的树尽量变成矮胖的树，这样B树就诞生了。

15.1 B 树

B-tree就是我们常说的B树，B树是一种平衡多路搜索树，B树与红黑树最大的不同在于，B树的结点可以有多个子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（l ogn），但可能比一棵红黑树的高度小许多，因为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。

m阶的B树满足以下性质：

（1）每个节点最多拥有m个子树；

（2）根节点最少有2个子树；

（3）分支节点最少拥有m/2棵子树；

（4）所有叶节点都在同一层，每个节点最多有m-1个key，并且以升序排列。

下图是一个M=4的4阶的B树：



B树的搜索：从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B树的特性：

1. 关键字集合分布在整颗树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束(树中所有结点都存储数据，与B+树这一点不同)；
4. 其搜索性能等价于在关键字全集内做一次二分查找；

15.1.1 B树查询流程

（1）获取根节点的关键字进行比较，当前根节点关键字为M，E要小于M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；

（2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；

（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

15.1.2 B树的插入节点流程

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：

1. 当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2） -1小于等于5-1（关键字数小于cei(5/2) -1就要进行节点合并，大于5-1就要进行节点拆分,非根节点关键字数>=2）；
2. 满足节点本身比左边节点大，比右边节点小的排序规则;
   
   
   
   
   
   

15.1.3 B树节点的删除

1. 当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)-1，小于等于5-1，非根节点关键字数大于2；
2. 满足节点本身比左边节点大，比右边节点小的排序规则;
3. 关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
   
   

15.2 B+树

B+树是对B树的一种变形，与B树的差异在于：

1. 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
4. 为所有叶子结点增加一个链指针，便于区间查找和遍历。
5. 所有关键字都在叶子结点出现。
6. B+跟B树不同，B+树的非叶子节点不保存关键字记录的指针，这样使得B+树每个节点所能保存的关键字大大增加；
7. B+树叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接；
8. B+树的根节点关键字数量和其子节点个数相等;
9. B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；
   
   

15.2.1 B+树的搜索

与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

15.2.2 B+的特性

1. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
2. B+树的叶子结点都是相链的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

15.2.3 B+树的分裂

1. 当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；
2. B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

15.2.4 特点

在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定;

15.3 B*树

B

树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B

树是B+树的变种，相对于B+树他们的不同之处如下：

1. 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b
   
   树的初始化个数为（cei(2/3
   
   m)）
2. B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；
   
   

15.3.1 特点

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

15.3.2 B*树的分裂

1. 当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；
2. 如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

16 树类结构总结

动态查找树主要有：二叉查找树、平衡二叉树、红黑树、B树、B+树。前面三种是典型的二叉查找树，查找的时间复杂度是O(log2N)。涉及到磁盘的读写（比如每个节点都需要从磁盘获取），读写的速度就与树的深度有关系，那么降低树的深度也就可以提升查找效率。这时就提出了平衡多路查找树，也就是B树以及B+树。

B树和B+树的非常典型的场景就是用于关系型数据库的索引。

从平衡二叉树、B树、B+树、B

树，总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度。

不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理，进行一步一步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的。

B树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B

树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

B+树虽然优点很多，但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：

16.1 为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引？

16.1.1 B+tree的磁盘读写代价更低

B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

16.1.2 B+tree的查询效率更加稳定

1. 由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
2. B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

17 LSM 树

LSM树，即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的，只是具体的实现不同。

LSM树核心思想的核心就是放弃部分读能力，换取写入的最大化能力。LSM Tree ，这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在内存中，等到积累到足够多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。

日志结构的合并树（LSM-tree）是一种基于硬盘的数据结构，与B+tree相比，能显著地减少硬盘磁盘臂的开销，并能在较长的时间提供对文件的高速插入（删除）。然而LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。

讲LSM树之前，需要提下三种基本的存储引擎，这样才能清楚LSM树的由来：

17.1 存储引擎

17.1.1 哈希存储引擎

是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是your Mr.Right

17.1.2 B树存储引擎

1. B树存储引擎是B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。
2. LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
   
   LSM树（Log Structured Merge Tree，结构化合并树）的思想非常朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘（由此提升了写性能），是一种基于硬盘的数据结构，与B-tree相比，能显著地减少硬盘磁盘臂的开销。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
   
   读取时需要合并磁盘中的历史数据和内存中最近的修改操作,读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件（存储在磁盘中的是许多小批量数据，由此降低了部分读性能。但是磁盘中会定期做merge操作，合并成一棵大树，以优化读性能）。LSM树的优势在于有效地规避了磁盘随机写入问题，但读取时可能需要访问较多的磁盘文件。
   
   核心思想的核心就是放弃部分读能力，换取写入的最大化能力，放弃磁盘读性能来换取写的顺序性。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

17.2 与B+树的差异

LSM树和B+树的差异主要在于读性能和写性能进行权衡。在牺牲的同时寻找其余补救方案：

1. LSM具有批量特性，存储延迟。当写读比例很大的时候（写比读多），LSM树相比于B树有更好的性能。因为随着insert操作，为了维护B+树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。
2. B树的写入过程：对B树的写入过程是一次原位写入的过程，主要分为两个部分，首先是查找到对应的块的位置，然后将新数据写入到刚才查找到的数据块中，然后再查找到块所对应的磁盘物理位置，将数据写入去。当然，在内存比较充足的时候，因为B树的一部分可以被缓存在内存中，所以查找块的过程有一定概率可以在内存内完成，不过为了表述清晰，我们就假定内存很小，只够存一个B树块大小的数据吧。可以看到，在上面的模式中，需要两次随机寻道（一次查找，一次原位写），才能够完成一次数据的写入，代价还是很高的。
3. LSM优化方式：
   
   Bloom filter: 就是个带随机概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
   
   compact:小树合并为大树:因为小树性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了

17.3 LSM树诞生背景

传统关系型数据库使用b-tree或一些变体作为存储结构，能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远（索引使用B-tree，数据使用行存储，按添加顺序保存），这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。

17.4 LSM树原理

LSM树由两个或以上的存储结构组成，比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中，称为C0 tree，具体可以是任何方便健值查找的数据结构，比如红黑树、map之类，甚至可以是跳表。另外一个存储结构常驻在硬盘中，称为C1 tree，具体结构类似B树。C1所有节点都是100%满的，节点的大小为磁盘块大小。

17.5 插入步骤

大体思路是：插入一条新纪录时，首先在日志文件中插入操作日志，以便后面恢复使用，日志是以append形式插入，所以速度非常快；将新纪录的索引插入到C0中，这里在内存中完成，不涉及磁盘IO操作；当C0大小达到某一阈值时或者每隔一段时间，将C0中记录滚动合并到磁盘C1中；对于多个存储结构的情况，当C1体量越来越大就向C2合并，以此类推，一直往上合并Ck。

17.6 合并步骤

合并过程中会使用两个块：emptying block和filling block。

从C1中读取未合并叶子节点，放置内存中的emptying block中。从小到大找C0中的节点，与emptying block进行合并排序，合并结果保存到filling block中，并将C0对应的节点删除。不断执行第2步操作，合并排序结果不断填入filling block中，当其满了则将其追加到磁盘的新位置上，注意是追加而不是改变原来的节点。合并期间如故宫emptying block使用完了则再从C1中读取未合并的叶子节点。C0和C1所有叶子节点都按以上合并完成后即完成一次合并。

17.7 插入操作

向LSM树中插入A E L R U，首先会插入到内存中的C0树上，这里使用AVL树，插入“A”，先向磁盘日志文件追加记录，然后再插入C0，

插入“E”，同样先追加日志再写内存，

继续插入“L”，旋转后如下，

插入“R”“U”，旋转后最终如下。

假设此时触发合并，则因为C1还没有树，所以emptying block为空，直接从C0树中依次找最小的节点。filling block长度为4，这里假设磁盘块大小为4。

开始找最小的节点，并放到filling block中，

继续找第二个节点，

以此类推，填满filling block，

开始写入磁盘，C1树，

继续插入B F N T，先分别写日志，然后插入到内存的C0树中，

假如此时进行合并，先加载C1的最左边叶子节点到emptying block，

接着对C0树的节点和emptying block进行合并排序，首先是“A”进入filling block，

然后是“B”，

合并排序最终结果为，

将filling block追加到磁盘的新位置，将原来的节点删除掉，

继续合并排序，再次填满filling block，

将filling block追加到磁盘的新位置，上一层的节点也要以磁盘块（或多个磁盘块）大小写入，尽量避开随机写。另外由于合并过程可能会导致上层节点的更新，可以暂时保存在内存，后面在适当时机写入。

17.8 查找操作

查找总体思想是先找内存的C0树，找不到则找磁盘的C1树，然后是C2树，以此类推。

假如要找“B”，先找C0树，没找到。

接着找C1树，从根节点开始，

找到“B”。

17.9 删除操作

删除操作为了能快速执行，主要是通过标记来实现，在内存中将要删除的记录标记一下，后面异步执行合并时将相应记录删除。

比如要删除“U”，假设标为#的表示删除，则C0树的“U”节点变为，

而如果C0树不存在的记录，则在C0树中生成一个节点，并标为#，查找时就能在内存中得知该记录已被删除，无需去磁盘找了。比如要删除“B”，那么没有必要去磁盘执行删除操作，直接在C0树中插入一个“B”节点，并标为#。

假如对写操作的吞吐量比较敏感，可采用日志策略（顺序读写，只追加不修改）来提升写性能。存在问题：数据查找需要倒序扫描，花费很多时间。比如，预写日志WAL，WAL的中心概念是数据文件（存储着表和索引）的修改必须在这些动作被日志记录之后才被写入，即在描述这些改变的日志记录被刷到持久存储以后。如果我们遵循这种过程，我们不需要在每个事务提交时刷写数据页面到磁盘，因为我们知道在发生崩溃时可以使用日志来恢复数据库：任何还没有被应用到数据页面的改变可以根据其日志记录重做（这是前滚恢复，也被称为REDO）。使用WAL可以显著降低磁盘的写次数，因为只有日志文件需要被刷出到磁盘以保证事务被提交，而被事务改变的每一个数据文件则不必被刷出。

其只是提高了写的性能，对于更为复杂的读性能，需要寻找其他的方法，其中有四种方法来提升读性能：

1. 二分查找: 将文件数据有序保存，使用二分查找来完成特定key的查找。
2. 哈希：用哈希将数据分割为不同的bucket
3. B+树：使用B+树 或者 ISAM 等方法，可以减少外部文件的读取
4. 外部文件： 将数据保存为日志，并创建一个hash或者查找树映射相应的文件。
   
   所有的四种方法都可以有效的提高了读操作的性能（最少提供了O(log(n)) )，但是，却丢失了日志文件超好的写性能，上面这些方法，都强加了总体的结构信息在数据上，数据被按照特定的方式放置，所以可以很快的找到特定的数据，但是却对写操作不友善，让写操作性能下降。更糟糕的是，当需要更新hash或者B+树的结构时，需要同时更新文件系统中特定的部分，这就是造成了比较慢的随机读写操作，这种随机的操作要尽量减少。
   
   既要保证日志文件好的写性能，又要在一定程度上保证读性能，所以LSM-Tree应运而生。

17.10 LSM操作

LSM树插入数据可以看作是一个N阶合并树。数据写操作（包括插入、修改、删除也是写）都在内存中进行，数据首先会插入内存中的树。当内存树的数据量超过设定阈值后，会进行合并操作。合并操作会从左至右便利内存中树的子节点与磁盘中树的子节点并进行合并，会用最新更新的数据覆盖旧的数据（或者记录为不同版本）。当被合并合并数据量达到磁盘的存储页大小时。会将合并后的数据持久化到磁盘，同时更新父节点对子节点的指针。

LSM树读数据 磁盘中书的非子节点数据也被缓存到内存中。在需要进行读操作时，总是从内存中的排序树开始搜索，如果没有找到，就从磁盘上的排序树顺序查找。

在LSM树上进行一次数据更新不需要磁盘访问，在内存即可完成，速度远快于B+树。当数据访问以写操作为主，而读操作则集中在最近写入的数据上时，使用LSM树可以极大程度地减少磁盘的访问次数，加快访问速度。

LSM树删除数据前面讲了。LSM树所有操作都是在内存中进行的，那么删除并不是物理删除。而是一个逻辑删除，会在被删除的数据上打上一个标签，当内存中的数据达到阈值的时候，会与内存中的其他数据一起顺序写入磁盘。 这种操作会占用一定空间，但是LSM-Tree 提供了一些机制回收这些空间。

17.11 特点

总的来说就是通过将大量的随机写转换为顺序写，从而极大地提升了数据写入的性能，虽然与此同时牺牲了部分读的性能。只适合存储 key 值有序且写入大于读取的数据，或者读取操作通常是 key 值连续的数据。

17.12 存储模型

17.12.1 WAL

WAL（write ahead log）也称预写log，包括mysql的Binlog等,在设计数据库的时候经常被使用，当插入一条数据时，数据先顺序写入 WAL 文件中，之后插入到内存中的 MemTable 中。这样就保证了数据的持久化，不会丢失数据，并且都是顺序写，速度很快。当程序挂掉重启时，可以从 WAL文件中重新恢复内存中的 MemTable。

17.12.2 MemTable

MemTable 对应的就是 WAL 文件，是该文件内容在内存中的存储结构，通常用 SkipList 来实现。MemTable 提供了 k-v 数据的写入、删除以及读取的操作接口。其内部将 k-v 对按照 key 值有序存储，这样方便之后快速序列化到 SSTable 文件中，仍然保持数据的有序性。

17.12.3 Immutable Memtable

顾名思义，Immutable Memtable 就是在内存中只读的 MemTable，由于内存是有限的，通常我们会设置一个阀值，当 MemTable 占用的内存达到阀值后就自动转换为 Immutable Memtable，Immutable Memtable 和 MemTable 的区别就是它是只读的，系统此时会生成新的 MemTable 供写操作继续写入。之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

17.12.4 SSTable

SSTable 就是 MemTable 中的数据在磁盘上的有序存储，其内部数据是根据 key 从小到大排列的。通常为了加快查找的速度，需要在 SSTable 中加入数据索引，可以快读定位到指定的 k-v 数据。

SSTable 通常采用的分级的结构，例如 LevelDB 中就是如此。MemTable 中的数据达到指定阀值后会在 Level 0 层创建一个新的 SSTable。当某个 Level 下的文件数超过一定值后，就会将这个 Level 下的一个 SSTable 文件和更高一级的 SSTable 文件合并，由于 SSTable 中的 k-v 数据都是有序的，相当于是一个多路归并排序，所以合并操作相当快速，最终生成一个新的 SSTable 文件，将旧的文件删除，这样就完成了一次合并过程。

17.13 LSM tree的写入

1，当收到一个写请求时，会先把该条数据记录在WAL Log里面，用作故障恢复。

2，当写完WAL Log后，会把该条数据写入内存的SSTable里面（删除是墓碑标记，更新是新记录一条的数据），也称Memtable。注意为了维持有序性在内存里面可以采用红黑树或者跳跃表相关的数据结构。

3，当Memtable超过一定的大小后，会在内存里面冻结，变成不可变的Memtable，同时为了不阻塞写操作需要新生成一个Memtable继续提供服务。

4，把内存里面不可变的Memtable给dump到到硬盘上的SSTable层中，此步骤也称为Minor Compaction，这里需要注意在L0层的SSTable是没有进行合并的，所以这里的key range在多个SSTable中可能会出现重叠，在层数大于0层之后的SSTable，不存在重叠key。

5，当每层的磁盘上的SSTable的体积超过一定的大小或者个数，也会周期的进行合并。此步骤也称为Major Compaction，这个阶段会真正的清除掉被标记删除掉的数据以及多版本数据的合并，避免浪费空间，注意由于SSTable都是有序的，我们可以直接采用merge sort进行高效合并。

17.14 LSM tree的读取

LSM Tree 的读取效率并不高，当需要读取指定 key 的数据时，先在内存中的 MemTable 和 Immutable MemTable 中查找，如果没有找到，则继续从 Level 0 层开始，找不到就从更高层的 SSTable 文件中查找，如果查找失败，说明整个 LSM Tree 中都不存在这个 key 的数据。如果中间在任何一个地方找到这个 key 的数据，那么按照这个路径找到的数据都是最新的。

在每一层的 SSTable 文件的 key 值范围是不重复的，所以只需要查找其中一个 SSTable 文件即可确定指定 key 的数据是否存在于这一层中。Level 0 层比较特殊，因为数据是 Immutable MemTable 直接写入此层的，所以 Level 0 层的 SSTable 文件的 key 值范围可能存在重复，查找数据时有可能需要查找多个文件。

17.15 读取的优化

因为这样的读取效率非常差，通常会进行一些优化，例如 LevelDB 中的 Mainfest 文件，这个文件记录了 SSTable 文件的一些关键信息，例如 Level 层数，文件名，最小 key 值，最大 key 值等，这个文件通常不会太大，可以放入内存中，可以帮助快速定位到要查询的 SSTable 文件，避免频繁读取。

1.1.1. 压缩

SSTable 是可以启用压缩功能的，并且这种压缩不是将整个 SSTable 一起压缩，而是根据 locality 将数据分组，每个组分别压缩，这样的好处当读取数据的时候，我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。

1.1.2. 缓存

因为SSTable在写入磁盘后，除了Compaction之外，是不会变化的，所以我可以将Scan的Block进行缓存，从而提高检索的效率

1.1.3. 索引

正常情况下，一个读操作是需要读取所有的 SSTable 将结果合并后返回的，但是对于某些 key 而言，有些 SSTable 是根本不包含对应数据的，因此，我们可以对每一个 SSTable 添加 Bloom Filter，因为布隆过滤器在判断一个SSTable不存在某个key的时候，那么就一定不会存在，利用这个特性可以减少不必要的磁盘扫描。

1.1.4. 合并

这个在前面的写入流程中已经介绍过，通过定期合并瘦身， 可以有效的清除无效数据，缩短读取路径，提高磁盘利用空间。但Compaction操作是非常消耗CPU和磁盘IO的，尤其是在业务高峰期，如果发生了Major Compaction，则会降低整个系统的吞吐量，这也是一些NoSQL数据库，比如Hbase里面常常会禁用Major Compaction，并在凌晨业务低峰期进行合并的原因。

最后有的同学可能会问道，为什么LSM不直接顺序写入磁盘，而是需要在内存中缓冲一下？ 这个问题其实很容易解答，单条写的性能肯定没有批量写来的块，这个原理其实在Kafka里面也是一样的，虽然kafka给我们的感觉是写入后就落地，但其实并不是，本身是 可以根据条数或者时间比如200ms刷入磁盘一次，这样能大大提升写入效率。此外在LSM中，在磁盘缓冲的另一个好处是，针对新增的数据，可以直接查询返回，能够避免一定的IO操作。

17.16 总结

简单的说，LSM-Tree牺牲了部分读取的性能，通过批量顺序写来换取了高吞吐的写性能，这种特性在大数据领域得到充分了体现，最直接的例子就各种NoSQL在大数据领域的应用，学习和了解LSM-Tree的结构将有助于我们更加深入的去理解相关NoSQL数据库的实现原理，掌握隐藏在这些框架下面的核心知识。

18 B+Tree VS LSM-Tree

传统关系型数据采用的底层数据结构是B+树，那么同样是面向磁盘存储的数据结构LSM-Tree相比B+树有什么异同之处呢？

LSM-Tree的设计思路是，将数据拆分为几百M大小的Segments，并是顺序写入。

B+Tree则是将数据拆分为固定大小的Block或Page, 一般是4KB大小，和磁盘一个扇区的大小对应，Page是读写的最小单位。

在数据的更新和删除方面，B+Tree可以做到原地更新和删除，这种方式对数据库事务支持更加友好，因为一个key只会出现一个Page页里面，但由于LSM-Tree只能追加写，并且在L0层key的rang会重叠，所以对事务支持较弱，只能在Segment Compaction的时候进行真正地更新和删除。

因此LSM-Tree的优点是支持高吞吐的写（可认为是O（1）），这个特点在分布式系统上更为看重，当然针对读取普通的LSM-Tree结构，读取是O（N）的复杂度，在使用索引或者缓存优化后的也可以达到O（logN）的复杂度。

而B+tree的优点是支持高效的读（稳定的OlogN），但是在大规模的写请求下（复杂度O(LogN)），效率会变得比较低，因为随着insert的操作，为了维护B+树结构，节点会不断的分裂和合并。操作磁盘的随机读写概率会变大，故导致性能降低。

还有一点需要提到的是基于LSM-Tree分层存储能够做到写的高吞吐，带来的副作用是整个系统必须频繁的进行compaction，写入量越大，Compaction的过程越频繁。而compaction是一个compare & merge的过程，非常消耗CPU和存储IO，在高吞吐的写入情形下，大量的compaction操作占用大量系统资源，必然带来整个系统性能断崖式下跌，对应用系统产生巨大影响，当然我们可以禁用自动Major Compaction，在每天系统低峰期定期触发合并，来避免这个问题。

阿里为了优化这个问题，在X-DB引入了异构硬件设备FPGA来代替CPU完成compaction操作，使系统整体性能维持在高水位并避免抖动，是存储引擎得以服务业务苛刻要求的关键。

19 LSM和WAL

在计算机科学中，预写式日志（Write-ahead logging，缩写 WAL）是关系数据库系统中用于提供原子性和持久性（ACID属性中的两个）的一系列技术。在使用WAL的系统中，所有的修改在提交之前都要先写入log文件中。

log文件中通常包括redo和undo信息。这样做的目的可以通过一个例子来说明。假设一个程序在执行某些操作的过程中机器掉电了。在重新启动时，程序可能需要知道当时执行的操作是成功了还是部分成功或者是失败了。如果使用了WAL，程序就可以检查log文件，并对突然掉电时计划执行的操作内容跟实际上执行的操作内容进行比较。在这个比较的基础上，程序就可以决定是撤销已做的操作还是继续完成已做的操作，或者是保持原样。

WAL允许用in-place方式更新数据库。另一种用来实现原子更新的方法是shadow paging，它并不是in-place方式。用in-place方式做更新的主要优点是减少索引和块列表的修改。ARIES是WAL系列技术常用的算法。在文件系统中，WAL通常称为journaling。PostgreSQL也是用WAL来提供point-in-time恢复和数据库复制特性。

所以基于此，LSM（log-structured merge-tree）就是充分利用了这一技术。输入的数据首先被存储在日志文件当中，这些文件完全有序。当日志文件被修改时，对应的更新会被先保存在内存当中用来加速查询。

当经历了很多次的数据修改之后，内存空间逐渐被占满，LSM树就会把这些数据作为一个新的数据写入到（磁盘）存储文件当中。同时由于最近的修改被持久化了，内存中的最近更新就可以被丢弃了。

写入到磁盘上的存储文件组织和B+树相似。当磁盘上的存储文件越来越多，系统就会进行合并处理。

20 总结

目前常见的主要的三种存储引擎是：哈希、B+树、LSM树：

哈希存储引擎 是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表性能最好。

B+树存储引擎 是B+树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。

LSM树（Log-Structured MergeTree）存储引擎 和B+树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。

21 案例

21.1 Hbase中存储设计主要思想

LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：

因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog；

MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

21.2 MYSQL

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

看一个例子：



图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在(O(log_2n))的复杂度内获取到相应数据。

innodb的主键索引都是聚簇索引,聚簇索引把数据行放在索引数据结构的叶子节点上,一个表只能有一个聚簇索引. 如果没有主键, Innodb会选择一个唯一的非空索引代替,如果没有这样的索引,Innodb会隐含的定义一个主键来作为聚簇索引。

首先我们看看聚簇索引在磁盘中的存储方式,如下图:

注意: 上图中非叶子节点只保存了索引列,叶子节点保存了索引列和数据行。

21.2.1 聚簇索引的优点

1. 数据访问更快, 聚簇索引把数据和索引保存在同一个B-tree中,索引命中即意味中数据全部命中。
2. 使用覆盖索引的扫描的查询可以直接使用页节点中的主键值.

21.2.2 缺点如下

1. 聚簇索引最大限度的提高了I/O密集型应用的性能.

2. 2, 插入速度严重依赖插入顺序.

3. 3, 更新聚簇索引列的代价很高,因为需要移位.

4. 4, 插入新数据时,或者主键裂需要移动的时候,可能面临“页分裂”.

5. 5, 非聚簇索引(二级索引)包含了聚簇索引,如果聚簇索引较大,二级索引也会很大(二级索引的叶子节点包含了主键列的值).
   
   那么二级索引列 money的存储结构又是怎么样的呢?
   
   
   
   可以看出,innodb的二级索引是直接在叶子节点存储了聚簇索引的值。
   
   二级索引的叶子节点保存的不是指向行的物理位置指针,而是行的主键值.这样行的在面临页分裂时,不需要单独维护二级索引。
   
   而MyISAM存储引擎则是主键索引和其它二级索引一样都指向了行数据。
   
   经过上面的讨论,我们应该大致清楚了,mysql表里的数据是如何在磁盘中存储的。