各种树

2018-12-04

红黑树

image.png

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

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

B树

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

• 树中每个结点至多有m个孩子；
• 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子；
• 若根结点不是叶子结点，则至少有2个孩子；
• 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
• 每个非终端结点中包含有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

B+树

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

image.png

1、B+树的磁盘读写代价更低
 磁盘是可以块存储的，也就是同一个磁道上同一盘块中的所有数据都可以一次全部读取。而B+树的内部结点并没有指向关键字具体信息的指针(比如文件内容的具体地址)，因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。这样，一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2、B+树的查询效率更加稳定。
 由于B+树非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须从根结点到叶子结点。所有关键字查询的路径长度相同，所以每一个数据的查询效率相当。

B+树最大的性能问题是会产生大量的随机IO，随着新数据的写入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。

LSM 树

把一颗大树拆分成N棵小树， 它首先写入到内存中，在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。当读时，需要合并磁盘中历史数据和内存中最近修改操作，由于不知道数据在哪棵小树上，因此必须遍历所有的小树，但在每颗小树内部数据是有序的。

image.png

• LSM引入了WAL，为什么要有WAL（Write Ahead Log）？因为数据是先写到内存中，如果断电，内存中的数据会丢失，因此为了保护内存中的数据，需要在磁盘上先记录logfile，当内存中的数据flush到磁盘上时，就可以抛弃相应的Logfile。
• 什么是memstore, storefile？很简单，上面说过，LSM树就是一堆小树，在内存中的小树即memstore，每次flush，内存中的memstore变成磁盘上一个新的storefile。
• 为什么会有compact？很简单，随着小树越来越多，读的性能会越来越差，因此需要在适当的时候，对磁盘中的小树进行merge，多棵小树变成一颗大树。
  优化
  a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
  b、compact:小树合并为大树。因为小树性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了

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

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

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