1. B树

二叉树的深度较大，在查找时会造成I/O读写频繁，查询效率低下，所以引入了多叉树的结构，也就是B树。关于B树的由来，wiki上阐述了B-tree名字来源以及相关的开源地址。

阶为M的B树具有以下性质：

排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
子节点数：非叶节点的子节点数>1，且<=M （M>=2），空树除外（注：M阶代表一个树节点最多有多少个查找路径，当M=2则是2叉树，M=3则是3叉）；
关键字数：子节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数如ceil(1.1)结果为2);
所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null，对应下图最后一层节点的空格子;

2. B+树

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

B+树通常用于数据库和操作系统的文件系统中。特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入。

B+树是B树的变体，也是一种多路搜索树，其定义基本与B树相同，不同如下：

B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；所有的非叶子结点可以看成是索引部分，结点中仅含有其子树（根结点）中最大（或最小）关键字
B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针；
非叶子节点的子节点数=关键字数（Mysql 的B+树）
为所有叶子结点增加一个链指针

3. B VS B+

B+树的优点：

1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树优点：

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

4. 红黑树

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用

一棵二叉树如果满足下面的红黑性质，则为一棵红黑树：

1、每个结点或是红的，或是黑的。
2、根结点是黑的。
3、每个叶结点 (NIL) 是黑的。
4、如果一个结点是红的，则它的两个儿子都是黑的。

性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑相间，树的高度为 2(N - 1) 。

5、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点

性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。

红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端性能略差。

红黑树的插入、删除调整逻辑比较复杂，但最终目的是满足红黑树的 5 个特性，尤其是 4 和 5。

插入、删除等详细操作，参考：https://juejin.im/entry/58371f13a22b9d006882902d

4.1. 应用

1、广泛用在C++的STL中。map和set都是用红黑树实现的。
2、著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
3、epoll在内核中的实现，用红黑树管理事件块
4、nginx中，用红黑树管理timer等
5、Java的TreeMap实现

5. RB vs B

RB树的深度较高，在磁盘I/O方面的表现不如B树。树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定。

所以，在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树表现相对优异，B树可以有多个子女，从几十到上千，可以降低树的高度。

6. AVL树

直接见我之前写的博客：https://blog.csdn.net/xiaqunfeng123/article/details/24093379

定义：

1、左子树和右子树都是AVL树
2、左子树和右子树的高度差不超过1 ，|HL-HR|<=1

性质：

1、一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)

2、一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).

3、一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

7. LSM tree

LSM Tree(Log Structured Merge Trees)数据组织方式被应用于多种数据库，如LevelDB、HBase、Cassandra等。

LSM tree相较B+树或其他索引存储实现方式，提供了更好的写性能。

7.1. 读写的平衡

顺序操作磁盘的性能，较随机读写磁盘的性能高很多，我们实现数据库时，也是围绕磁盘的这点特性进行设计与优化。如果让写性能最优，最佳的实现方式就是日志型(Log/Journal)数据库，其以追加(Append)的方式写磁盘文件。

带来最优写性能的同时，单纯的日志数据库读性能很差，为找到一条数据，不得不遍历数据记录，要实现范围查询(range)几乎不可能。为优化日志型数据库的读性能，实际应用中通常结合以下几种优化措施：

二分查找(Binary Search): 在一个数据文件中使用二分查找加速数据查找
哈希(Hash): 写入时通过哈希函数将数据放入不同的桶中，读取时通过哈希索引直接读取
B+树: 使用B+树作为数据组织存储形式，保持数据稳定有序
外部索引文件: 除数据本身按日志形式存储外，另对其单独建立索引加速读取

以上措施都很大程度提升了读性能(如二分查找将时间复杂度提升至O(log(N)))，但相应写性能也有折损：

第一写数据时需要维护索引，这视索引的实现方式，最差情况下可能涉及随机的IO操作；
第二如果用B+树等结构组织数据，写入涉及两次IO操作，先要将数据读出来再写入。

7.2. LSM tree的引出

LSM tree存储实现思路与以上四种措施不太相同，其将随机写转化为顺序写，尽量保持日志型数据库的写性能优势，并提供相对较好的读性能。具体实现方式如下：

当有写操作(或update操作)时，写入位于内存的buffer，内存中通过某种数据结构(如skiplist)保持key有序
一般的实现也会将数据追加写到磁盘Log文件，以备必要时恢复
内存中的数据定时或按固定大小地刷到磁盘，更新操作只不断地写到内存，并不更新磁盘上已有文件
随着越来越多写操作，磁盘上积累的文件也越来越多，这些文件不可写且有序
定时对文件进行合并操作(compaction)，消除冗余数据，减少文件数量

LSM Tree的树节点可以分为两种，保存在内存中的称之为MemTable，保存在磁盘上的称之为SSTable。

7.3. 写操作

只需更新内存，内存中的数据以块数据形式刷到磁盘，是顺序的IO操作

写操作直接作用于MemTable，因此写入性能接近写内存

每层SSTable文件到达一定条件后，进行合并操作，然后放置到更高层

Level 0可以认为是MemTable的文件映射内存, 因此每个Level 0的SSTable之间的key range可能会有重叠。其他Level的SSTable key range不存在重叠。
Level 0的写入是简单的创建-->顺序写流程，因此理论上，写磁盘的速度可以接近磁盘的理论速度。

7.4. 合并

合并操作是LSM tree实现中重要的一环，LevelDB、Cassandra中，使用基于层级的合并方式(Levelled compaction)，生成第N层的时候，对N-1层的数据进行排序，使得每层内的数据文件之间都是有序的，但最高层除外，因为该层不断有数据文件产生，因而只是数据文件内部按key有序。

SSTable合并类似于简单的归并排序：根据key值确定要merge的文件，然后进行合并。因此，合并一个文件到更高层，可能会需要写多个文件。存在一定程度的写放大。是非常昂贵的I/O操作行为。

7.5. 读操作

先从内存数据开始访问，如果在内存中访问不到，再顺序从一个个磁盘文件中查找，由于文件本身有序，并且定期的合并减少了磁盘文件个数，因而查找过程相对较快速。

读操作优先判断key是否在MemTable, 如果不在的话，则把覆盖该key range的所有SSTable都查找一遍。简单，但是低效。

复杂度

除最高层外，其他层文件间数据有序，这也加速了读过程，因为一个key对应的value只存在一个文件中。假设总共有N层，每层最多K个数据文件，最差的情况下，读操作先遍历K个文件，再遍历每层，共需要K+(N-1)次读盘操作。

在工程实现上，一般会为SSTable加入索引。可以是一个key-offset索引（类似于kafka的index文件），也可以是布隆过滤器（Bloom Filter）。

7.6. 适用场景

LSM tree适用于写多、读相对少(或较多读取最新写入的数据，该部分数据存在内存中，不需要磁盘IO操作)的业务场景。

LSM Tree (Log-structured merge-tree)，是一种分层的组织数据的结构，具体到实际实现上，就是一些按照逻辑分层的有序文件。

参考资料：http://www.cnblogs.com/bangerlee/p/4307055.html

https://liudanking.com/arch/lsm-tree-summary/

8. skiplist

跳跃列表是一种随机化数据结构，基于并联的链表，其效率可比拟二叉查找树。

有序链表，查找的时间复杂度为O(n)，尽管真正的插入与删除操作节点复杂度只有O(1)，但都需要先查找到节点的位置，可以说是查找拉低了有序链表的性能。

如果是数组的话，可以使用二分查找达到O(lgn)。

可以在链表中使用二分查找吗？

不可以，因为二分查找需要用到中间位置的节点，而链表不能随机访问。

那么就把中间位置的节点单独保存吧。

所以SkipList应运而生，就是额外保存了二分查找的中间信息。

SkipList采用“空间换时间”的思想，除了原始链表外还保存一些“跳跃”的链表，达到加速查找的效果。

8.1. 特征

关于跳表，应该具有以下特征：

一个跳表应该有几个层（level）组成；
跳表的第一层包含所有的元素；
每一层都是一个有序的链表；
如果元素x出现在第i层，则所有比i小的层都包含x；
第i层的元素通过一个down指针指向下一层拥有相同值的元素；
在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；
Top指针指向最高层的第一个元素。

8.2. 示例

有序链表：

构建跳表:

构建步骤：

1、给定一个有序的链表。
2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。

8.3. skiplist与平衡树、哈希表的比较

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

树