查找结构(二叉树、红黑树、B树、B+树、LSM)

Posted on In

[toc]

二叉查找树

  二叉查找树（BST）又叫二叉排序树，二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 　　

  1. 若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
  2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 左、右子树也分别为二叉排序树；
  4. 没有键值相等的节点。

  平均情况下查找时间复杂度为O(logn)；最坏情况则是退化成一个链表，查找时间复杂度为O(n)。

​ 二叉树结构其查找的时间复杂度与树高相关。那么降低树高自然对查找效率是有所帮助的。另外还有一个比较实际的问题：对大数据存储的查询，平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。那么如何减少树的深度，一个基本的想法就是：

  • 每个节点存储多个元素
  • 摒弃二叉树结构，采用多叉树

  

平衡二叉树

  平衡二叉查找树，又称 AVL树。 它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子）不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。
  平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。二叉平衡树的严格平衡策略是以牺牲插入、删除的代价，换来了稳定的O(logN) 查找时间复杂度。

  但是平衡二叉树也有缺陷：
  (1)为了保证严格平衡(|bf|<=1)，每个插入和删除操作的代价也随之增加。红黑树将解决这个问题。
  (2)所有二叉查找树结构的查找代价都与树高是紧密相关的，能否通过减少树高来进一步降低查找代价呢？这个是可以通过多路查找树的结构来做到这一点。
  (3) 在大数据量查找环境下(比如说系统磁盘里的文件目录，数据库中的记录查询等)，所有的二叉查找树结构都不合适。如此大规模的数据量（几G数据），全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧？问题就来了：假如构造的平衡二叉树深度有1W层，那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。硬盘的机械部件读写数据的速度是远远赶不上内存。 查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下，平衡二叉树的效率就很成问题了。

  

红黑树

  红黑树(red-black tree) 是一棵满足下述性质的二叉查找树：

  1. 每一个结点要么是红色，要么是黑色。
  2. 根结点是黑色的。
  3. 所有叶子结点都是黑色的（实际上都是Null指针，下图用NIL表示）。叶子结点不包含任何关键字信息，所有查询关键字都在非终结点上。
  4. 每个红色结点的两个子节点必须是黑色的。从每个叶子到根的所有路径上不能有两个连续的红色结点。
  5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

  查找效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于二叉查找树。
  插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

    

B树

  B树，又叫平衡多路查找树。一棵m阶的B树 (m叉树)的特性如下：

  1. 树中每个结点至多有m个孩子；
  2. 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子；
  3. 若根结点不是叶子结点，则至少有2个孩子；
  4. 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
  5. 每个非终端结点中包含有n个关键字信息： (n，P1，K1，P2，K2，P3，……，Kn，Pn)。其中，
    　　a. Ki (i=1…n)为关键字，且关键字按顺序排序Ki < K(i-1)。
    　　　　　　　　　　　　b. Pi为指向子树根的结点，且指针Pi指向的子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
    　　　　　　　　　　　　c. 关键字的个数n必须满足： [m/2]-1 <= n <= m-1

  例如：下面就是一棵3阶B树:

B+树

  B+树是应文件系统所需而产生的一种B树的变形树。 一棵m阶的B+树和m阶的B树的差异在于：

  1. 有n棵子树的结点中含有n个关键字； (B树是n棵子树有n+1个关键字)
  2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B树的叶子节点并没有包括全部需要查找的信息)
  3. 所有的非叶子结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (B树的非叶子节点也包含需要查找的有效信息)
  4. B+树所有节点数据都能在叶子节点里找到，所以非叶子节点只需要存 索引范围和指向下一级索引（或者叶子节点）的地址 ，不需要存整行的数据，所以占用空间非常小，直到找到叶子节点才加载进来整行的数据。
  5. 叶子节点之间加了指针，形成了链表。（这里体现了B+树 select * 时的优势，B树需要做局部的中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了）

  例如：下面就是一棵3阶B+树。可以和B树做一个明显的对比。

  B+树的叶子结点包含了所有待查询关键字，而非叶子节点只是作为叶子结点中最大(最小)关键字的索引。因此B+树的非叶子结点没有文件内容所在物理存储的地址，而B树所有结点均有文件内容所在的磁盘物理地址（B树结构图中结点内部的小红方块）。 这个特点是B+树的一个重要优势所在。

B+树的优势所在

  为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？
  1、B+树的磁盘读写代价更低
  磁盘是可以块存储的，也就是同一个磁道上同一盘块中的所有数据都可以一次全部读取。而B+树的内部结点并没有指向关键字具体信息的指针(比如文件内容的具体地址)，因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。这样，一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

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

  2、B+树的查询效率更加稳定。
  由于B+树非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须从根结点到叶子结点。所有关键字查询的路径长度相同，所以每一个数据的查询效率相当。

​ B+Tree 是对读操作优化的存储结构，能够支持高效的范围扫描，叶节点之间保留链接并且按主键有序排列，扫描时避免了耗时的遍历树操作。下面这张图中展示了一棵高度为 2 的 B+Tree，数据存储在 5 个页表中，每页可存放 4 条记录。为了方便理解，略去了叶子节点指向数据的指针以及叶子节点之间的顺序指针。

image-20240717114131036

​ B+Tree 由内节点(InterNode)和叶节点(LeafNode)两类节点构成，前者仅包含索引信息，后者则携带了指向数据的指针。当插入一个索引值为 70 的记录，由于对应页表的记录已满，需要对 B+Tree 重新排列，变更其父节点所在页表的记录，并调整相邻页表的记录。完成重新分布后的效果如下:

image-20240717114218766

在这个写入过程中存在两个问题:

1. 写放大

本来仅需要一条写入记录(黄色标注)，实际上更新了 3 个页表中的 7 条索引记录，额外的 6 条记录(绿色标注)是为了维护 B+Tree 结构产生的写放大。

2. 存储不连续

虽然新增叶节点会加入到原有叶节点构成的有序链表中，整体在逻辑上是连续的，但是在磁盘存储上，新增页表申请的存储空间与原有页表很可能是不相邻的。这样，在后续包含新增叶节点的查询中，将会出现多段连续读取，磁盘寻址的时间将会增加。

也就是说，虽然 B+Tree 结构是为读取做了优化，但如果进行大量随机写还是会造成存储的碎片化，从而导致写放大和读放大。

填充因子(Factor Fill)是一种常见的优化方法，它的原理就是在页表中预留一些空间，这样不会因为少量的数据写入造成树结构的大幅变动。但填充因子的设置也很难拿捏，过大则无法解决写放大问题;过小会造成页表数量膨胀，增大对磁盘的扫描范围，降低查询性能。

 

LSM树

  B+树最大的性能问题是会产生大量的随机IO，随着新数据的写入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。为了克服B+树的弱点，HBase引入了LSM树的概念，即Log-Structured Merge-Trees。
  为了更好的说明LSM树的原理，下面举个比较极端的例子：现在假设有1000个节点的随机key，对于磁盘来说，肯定是把这1000个节点依次写入磁盘最快，但是这样一来，读就悲剧了，因为key在磁盘中完全无序，每次读取都要全扫描；那么，为了让读性能尽量高，数据在磁盘中必须得有序，这就是B+树的原理，但是写就悲剧了，因为会产生大量的随机IO，磁盘寻道速度跟不上。

  LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能，用来大幅提高写性能。
  LSM树的原理是把一颗大树拆分成N棵小树， 它首先写入到内存中，在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。当读时，需要合并磁盘中历史数据和内存中最近修改操作，由于不知道数据在哪棵小树上，因此必须遍历所有的小树，但在每颗小树内部数据是有序的。
img

  以上就是LSM树最本质的原理。
  1. LSM引入了WAL，为什么要有WAL（Write Ahead Log）？因为数据是先写到内存中，如果断电，内存中的数据会丢失，因此为了保护内存中的数据，需要在磁盘上先记录logfile，当内存中的数据flush到磁盘上时，就可以抛弃相应的Logfile。
  2. 什么是memstore, storefile？很简单，上面说过，LSM树就是一堆小树，在内存中的小树即memstore，每次flush，内存中的memstore变成磁盘上一个新的storefile。
  3. 为什么会有compact？很简单，随着小树越来越多，读的性能会越来越差，因此需要在适当的时候，对磁盘中的小树进行merge，多棵小树变成一颗大树。

​ 关于LSM Tree，对于最简单的二层LSM Tree而言，内存中的数据和磁盘中的数据merge操作，如下图:

img

  LSM Tree弄了很多个小的有序结构，比如每m个数据，在内存里排序一次，下m个数据，再排序一次……这样依次做下去，就可以获得N/m个有序的小的有序结构。
  在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。
  很容易可以看出，这样的模式，读取的时间复杂度是(N/m)*log2N 。读取效率是会下降的。
  这就是最本来意义上的LSM tree的思路。那么这样做，性能还是比较慢的，于是需要再做些事情来提升，怎么做才好呢？

LSM Tree优化方式

  a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
  b、compact:小树合并为大树。因为小树性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了

B+树与LSM树比较

  1. B+树的特点决定了能够对主键进行高效的查找和删除，B+树能够提供高效的的范围扫描功能得益于相互连接且按主键有序，扫描时避免了耗时的遍历操作。
  LSM树在查找时先查找内存的存储，如果在内存中未命中就去磁盘文件中查找文件，找到key之后返回最新的版本。
  B树和LSM树最主要的区别在于他们的结构和如何利用硬件，特别是磁盘。

  2. 在没有太多的修改时，B+树表现得很好，因为修改要求执行高代价的优化操作以保证查询能在有限的时间内完成。LSM以磁盘传输速率工作，并能较好地扩展以处理大量数据，他们使用日志文件和内存存储来将随机写转换成顺序写，因此也能够保证稳定的数据插入速率。由于读写分离，两个操作也不存在冲突的问题。

  3. LSM树的主要目标是快速的建立索引，B树是建立索引的通用技术，但是在大并发插入数据的情况下，B树需要大量的随机IO，这些随机IO严重影响索引建立速度。LSM通过磁盘序列写，来达到最优的写性能，因为这个降低了磁盘的寻道次数，一次IO可以写入多个索引块。

LSM 是分成三步完成了数据的落盘。
image-20240717114325893

  1. 第一步是写入 Memtable，同时记录 Tablet Log;
  2. 当 Memtable 的数据达到一定阈值后，系统会把其冻结并将其中的数据顺序写入磁盘上的有序文件(Sorted String Table，SSTable)中，这个操作被称为 Flush；当然，执行这个动作的同时，系统会同步创建一个新的 Memtable，处理写入请求。
  3. 根据第二步的处理逻辑，Memtable 会周期性地产生 SSTable。当满足一定的规则时，这些 SSTable 会被合并为一个大的 SSTable。这个操作称为 Compact。

​

与 B+Tree 的最大不同是 LSM 将随机写转换为顺序写，这样提升了写入性能。另外，Flush 操作不会像 B+Tree 那样产生写放大。Flush 是没有写放大，但还有 Compact 呢?

说的没错，真正的写放大就发生在 Compact 这个动作上。Compact 有两个关键点，一是选择什么时候执行，二是要将哪些 SSTable 合并成一个 SSTable。这两点加起来称为“合并策略”。

刚刚在例子中描述的就是一种合并策略，称为 Size-Tiered Compact Strategy，简称Tiered。BigTable 和 HBase 都采用了 Tiered 策略。它的基本原理是，每当某个尺寸的SSTable 数量达到既定个数时，将所有 SSTable 合并成一个大的 SSTable。这种策略的优点是比较直观，实现简单，但是缺点也很突出。

下面从 RUM 的三个角度来分析下:

1. 读放大

执行读操作时，由于单个 SSTable 内部是按照 Key 顺序排列的，那么查找方法的时间复杂度就是 O(logN)。因为 SSTable 文件是按照时间间隔产生的，在 Key 的范围上就会存在交叉，所以每次读操作都要遍历所有 SSTable。如果有 M 个 SSTable，整体时间复杂度就是O(MlogN))。执行Compact后，时间复杂度降低为O(log(MN))。在只有一个SSTable时，读操作没有放大。

2. 写放大

Compact 会降低读放大，但却带来更多的写放大和空间放大。其实 LSM 只是推迟了写放大，短时间内，可以承载大量并发写入，但如果是持续写入，则需要一部分 I/O 开销用于处理 Compact。

你可能听说到过关于 B+Tree 和 LSM 的一个争论，就是到底谁的写放大更严重。如果是采用 Tiered 策略，LSM 的写放大比 B+Tree 还严重。此外，Compact 是一个很重的操作，占用大量的磁盘 I/O，会影响同时进行的读操作。

3. 空间放大

从空间放大的角度看，Tiered 策略需要有两倍于数据大小的空间，分别存储合并前的多个SSTable 和合并后的一个 SSTable。

看到这你可能会觉得奇怪，LSM 好像也不是太优秀呀。只有短时间内写入速度快和阶段性的控制读放大这两个优势，在写放大和空间放大上都做得不好，而且还有 Compact 这种耗费 I/O 的重量级操作。那 LSM 为什么还这么流行呢?

这是因为 LSM 还有另一种合并策略，Leveled Compact Strategy，简称 Leveled 策略。

Leveled Compact Strategy

Tiered 策略之所以有严重的写放大和空间放大问题，主要是因为每次 Compact 需要全量数据参与，开销自然就很大。那么如果每次只处理小部分 SSTable 文件，就可以改善这个问题了。

Leveled 就是这个思路，它的设计核心就是将数据分成一系列 Key 互不重叠且固定大小的SSTable 文件，并分层(Level)管理。同时，系统记录每个 SSTable 文件存储的 Key 的范围。Leveled 策略最先在 LevelDB 中使用，也因此得名。后来从 LevelDB 上发展起来的RocksDB 也采用这个策略。

接下来，我们详细说明一下这个处理过程。

  1. 第一步处理 Leveled 和 Tiered 是一样的。当内存的数据较多时，就会 Flush 到SSTable 文件。对应内存的这一层 SSTable 定义为 L0，其他层的文件我们同样采用 Ln的形式表示，n 为对应的层数。因为 L0 的文件仍然是按照时间顺序生成的，所以文件之间就可能有重叠的 Key。L0 不做整理的原因是为了保证写盘速度。
    image-20240717114348162

  2. 通常系统会通过指定 SSTable 数量和大小的方式控制每一个层的数据总量。当 L0 超过预定文件数量，就会触发 L0 向 L1 的 Compact。因为在 L0 的 SSTable 中 Key 是交叉的，所以要读取 L0 的所有 SSTable，写入 L1，完成后再删除 L0 文件。从 L1 开始，SSTable 都是保证 Key 不重叠的。
    image-20240717114411195

  3. 随着 L1 层数据量的增多，SSTable 可能会重新划分边界，目的是保证数据相对均衡的存储。
    image-20240717114428115

​

  1. 由于 L1 的文件大小和数量也是受限的，所以随着数据量的增加又会触发 L1 向 L2 的Compact。因为 L1 的文件是不重叠的，所以不用所有 L1 的文件都参与 Compact，这就延缓了磁盘 I/O 的开销。而 L2 的单个文件容量会更大，通常从 L1 开始每层的存储数据量以 10 倍的速度增长。这样，每次 Ln 到 L(n+1) 的 compact 只会涉及少数的SSTable，间隔的时间也会越来越长。
    image-20240717114455291

说完处理流程，我们再从 RUM 三个角度来分析下。

1. 读放大

因为存在多个 SSTable，Leveled 策略显然是存在读放大的。因为 SSTable 是有序的，如果有 M 个文件，则整体计算的时间复杂度是 O(MlogN)。这个地方还可以优化。通常的方法是在 SSTable 中引入 Bloom Filter(BF)，这是一个基于概率的数据结构，可以快速地确定一个 Key 是否存在。这样执行 Get 操作时，先读取每一个 SSTable 的 BF，只有这个Key 存在才会真的去文件中查找。

那么对于多数 SSTable，时间复杂度是 O(1)。L0 层的 SSTable 无序，所有都需要遍历，而从 L1 层开始，每层仅需要查找一个 SSTable。那么优化后的整体时间复杂度就是O(X+L-1+logN)，其中 X 是 L0 的 SSTable 数量，L 是层数。

2. 写放大
Leveled 策略对写放大是有明显改善的，除了 L0 以外，每次更新仅涉及少量 SSTable。但是 L0 的 Compact 比较频繁，所以仍然是读写操作的瓶颈。

3. 空间放大
数据在同层的 SSTable 不重叠，这就保证了同层不会存在重复记录。而由于每层存储的数据量是按照比例递增的，所以大部分数据会存储在底层。因此，大部分数据是没有重复记录的，所以数据的空间放大也得到了有效控制。

OceanBase对Compact问题的优化
OceanBase 的存储模型基本上也是LSM，也就同样需要面对 Compact 带来的一系列问题。来看看 OceanBase 是怎么优化的。

宏块与微块
在 Compact 过程中，被合并文件中的所有数据都要重写到新文件中。其实，对于那些没有任何修改的数据，这个过程是可以被优化的。

OceanBase 引入了宏块与微块的概念，微块是数据的组织单元，宏块则由微块组成。这样在进行 Compact 操作时，可以在宏块和微块两个级别判断，是否可以复用。如果在这两个级别数据没有发生实质变化，则直接进行块级别的拷贝，这样就省去了更细粒度的数据解析、编码以及计算校验和(Checksum)等操作。

轮转合并
OceanBase 还在多副本基础上设计了轮转合并机制。我们知道，根据 Raft 协议或者Paxos 协议，总有多个副本同时存储着最新的数据，那么我们就可以用多副本来解耦Compact 操作和同时段的查询操作，避免磁盘 I/O 上的竞争。

它的大致设计思路是这样的，将 Compact 操作放在与 Leader 保持数据同步的 Follower上执行，而 Leader 节点则保持对外提供查询服务。当 Compact 完成后，改由那个Follower 对外提供查询服务，Leader 和其他副本则去执行 Compact。

OceanBase 的这两项优化虽然没有降低写放大系数，但却有效减少了 Compact 过程中的I/O 竞争。

TiDB:WiscKey
OceanBase 的优化还停留在工程层面，那么还有没有更好的理论模型呢?
2016 年真的出现了新的模型，这就是 WiscKey。WiscKey 提出的改进是通过将 value 分离出 LSM-Tree 的方法来降低写放大。
WiscKey 的主要设计思想是，在 SSTable 的重写过程中，核心工作是对 Key 进行整理，保证多个 SSTable 的 Key 范围不重叠，且内部有序。而这个过程中 Value 的重写是没有太大价值的，而从实践看，Value 占用的存储空间远远大于 Key。这意味着大量的写操作和空间成本被浪费了。所以 WiscKey 提出将 Value 从 SSTable 中分离出来单独存储，这样就降低了写放大系数。
image-20240717114511583

Value 单独存储的问题是按照 Key 连续读取数据时，对应的 Value 并不是连续存储，磁盘寻址成本增大。而 WiscKey 的设计前提是使用 SSD 替换 HDD，SSD 的随机读写效率接近于顺序读写，所以能够保持较高的整体效率。事实上，过高的写放大也会严重缩短 SSD的使用寿命。WiscKey 就是针对 SSD 提出的存储模型。

TiDB 和 Cockroach 放弃 RocksDB 的原因就是受到 WiscKey 的启发，TiDB 的新存储引擎 TiTan 目标之一就是将 Value 从LSM-Tree 中分离出来单独存储，以降低写放大。

转载自：
https://blog.csdn.net/laiwenqiang/article/details/40893157
https://www.cnblogs.com/bonelee/p/6244810.html