Tree-LSM

陆斌

2023-12-01

二分法

二分法很简单，很精妙！一半一半的舍弃，一倍一倍的填充。（O（LogN））->树

树的类型

什么是普通的树？

无序、混沌、自然、简单、墒减！

什么是动态查找树？

动态查找树主要有：二叉查找树(BST)，平衡二叉查找树(AVL)，红黑树(RBT)，B~/B+树(B-tree)。
其都是动态结构。在删除，插入操作的时候，都不需要彻底重建原始的索引树。最多就是执行一定量的旋转，变色操作来有限的改变树的形态。
其查找的时间复杂度大体维持在O(log(N))数量级上。可能有些结构在最差的情况下效率将会下降很快，比如：BST。

什么是二叉查找树（Binary Search Tree）/二叉排序树/二叉搜索树？

每个结点有key、卫星数据（需要存储的value）。还包含属性：lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。（二叉树）
若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；其他的左右子树也分别为二叉查找树；（左根右，中序遍历有序）
二叉查找树是动态查找树，在查找的过程中可添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。（在删除，插入操作的时候，都不需要彻底重建原始的索引树。）
查找、插入、删除的时间复杂度为O（logN），但是有极端情况，变为类似线性链表的结构，时间复杂度为O（N）。（不平衡）

什么是平衡树（Balance Tree）？

我们约定：任意节点的子树的高度差都小于等于1，即为平衡。（平衡）

AVL树

二叉平衡搜索（排序）树（AVL树）：AVL得名于其发明者的名字( Adelson-Velskii 以及 Landis)，是一种平衡二叉树。本质上是一棵二叉查找树。
平衡因子（Balance Factor，简写为bf）：结点的平衡因子 = 左子树的高度 - 右子树的高度，在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1。
插入保持平衡性，需要旋转操作：LL、LR、RL、RR。

红黑树

是一种特殊的二叉查找树。本质为2-3-4B树。

特点：

1. 每个节点是黑色或者红色。
2. 根节点是黑色的。
3. 叶子节点是黑色的。此处是指为NIL（NULL）的叶子节点。
4. 红色节点的子节点是黑色的，即红色节点不可以直接相邻。
5. 从一个节点到该节点的子孙节点的所有路径上，包含相同数目的黑色节点。（确保没有一条路径会比其他路径长出两倍，因而红黑树是相对接近平衡的二叉树）->插入节点为红色。

上述特点隐含的信息：
1. bh(x)值是唯一的，且节点x的亲子节点的黑高，（当x为红色）要么是bh(x)，（当x为黑色）要么是bh(x)-1。
2. 2bh(x)>h(x)，从节点x到叶子节点，所经历的黑色节点数目>=所经历的红色节点数目。

时间复杂度分析：数学归纳法

假设：一棵红黑树，树高为h(x)，黑色节点的高度为bh(x)，且叶子节点NIL（NULL）为黑色且高度为0，即bh(x)=0。
引理（人们研究总结发现的规律）：以结点x为根的红黑树树至少包含2^bh(x)-1个内节点（不包括叶子节点NIL（NULL））。即：高度为h(x)的红黑树，它包含的内节点个数至少为2^bh(x)-1个。（定理一）
证明：
1. 当仅有一个叶子节点NIL（NULL）时，bh(x)=0，内节点2^bh(x)-1=0，引理成立！
2. 当h(x)>0，bh(x)值唯一，且节点x的亲子节点的黑高，（当x为红色）要么是bh(x)，（当x为黑色）要么是bh(x)-1。
	此时：左子树和右子树内节点分别大于等于2^(bh(x)-1) - 1。
	又：任意一个节点的内结点=左子树内结点+右子树内结点+当前节点。
	且：2bh(x)>h(x)
	则：以结点x为根的树的内节点个数（假设n个） > 2^(bh(x)-1) - 1 + 2^(bh(x)-1) - 1 + 1 = 2^bh(x) - 1 > 2^(h(x)/2) - 1
	至此：引理得证！
	变换得：n + 1 > 2^(h(x)/2) -> 2log(n + 1) > h(x)
	即：一棵含有n个节点的红黑树，高度至多为 2log(n + 1)。（定理二）
	定理一与定理二互为逆否命题。
	特别的，当n趋向于无穷大，h(x) < 2log(n + 1) 等价于 h(x) < log(n)，即红黑树的时间复杂度为O(log(n))

实现：为了保持特点需要旋转和变色。

详见参考文档：
	普林斯顿大学算法公开课：平衡搜索树。

红黑树（RB-Tree）存在的意义：

AVL的平衡因子是其绝对值小于等于1，显然，红黑树不属于平衡搜索树。
但是红黑树引入了节点颜色的概念，放弃严格的平衡来换取旋转次数的降低，任何不平衡都会在三次旋转之内解决。所以，红黑树插入效率更高！

1. 插入node引起不平衡，AVL和RB-Tree都是最多两次旋转操作，O(1)时间复杂度，就可以恢复平衡。
2. 删除node引起不平衡，RB-Tree最多需要3次旋转，而AVL最坏情况需要维护从被删node到root路径上所有node的平衡性，因此需要旋转的量级O(logN)。
3. AVL平衡度高，所以search操作效率更高。但是大量数据插入和删除时，AVL需要rebalance的频率会更高！折衷来看，RB-Tree统计性能是高于AVL的。

应用：

1. Java集合中TreeSet和TreeMap。
2. Linux虚拟内存管理。

SBT（Size Balanced Tree）

我国的陈启峰提出的高度平衡的二叉树。

每个子树的大小大于所有侄子的大小：

s[T.right]≥s[T.left.left],s[T.left.right]
s[T.left]≥s[T.right.right],s[T.right.left]

SBT通过旋转来动态调整树的结构。
SBT能在O(log n)的时间内完成所有二叉搜索树（BST）的相关操作，而与普通二叉搜索树相比，SBT仅仅加入了简洁的核心操作Maintain。由于SBT赖以保持平衡的是size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank操作。

Treap

堆通常是一个可以被看做一棵树的数组对象。
堆总是一棵完全二叉树。
交换次数最大也为树的高度（log n）。

操作逻辑：

1. 当插入一个新值时，首先将值放到树的最后的位置。然后将这个值与父元素比较，如果不满足性质（大根堆/小根堆），则与父元素替换。
2. 查询时，可以把最后一个数放到头的位置，这样树的结构就不会改变（调整），而且操作简单。

伸展树

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。

核心思想：局部性原理

刚刚被访问过的元素，极有可能在不久之后被再次访问。
即将被访问的元素，极可能处于刚被访问元素的附近。
伸展树将每次刚被访问的结点通过旋转操作移到树根。
采用双层伸展。

左旋右旋的记忆方式：
对结点进行左旋操作，会将该结点变到其左孩子的位置，而其右孩子将变成其父亲，右旋则反之。

多路平衡搜索/查找树（B树、B+树、B-树）

B树：所有叶子结点位于同一层，关键字集合分布在整棵树中（区间查找和搜索需要对每一层递归遍历，可能导致相邻元素在内存中不相邻，所以缓存命中率没有B+树好），任何一个关键字出现且只出现在一个结点中，所以搜索有可能在非叶子结点结束，搜索性能等价于在关键字全集内做一次二分查找。（O（LogN））
B+树：所有叶子结点中包含了全部关键字信息，且叶子结点本身依关键字大小自小而大顺序链接，便于区间查找和遍历，非叶子结点存在意义是作为索引，性能等价于在关键字全集做一次二分查找。（O（LogN）)
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。
1. B+树 的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针。B+树 的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
2. B*树 的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

多路平衡搜索树存在的意义？

空间局部性原理：

如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。

减少磁盘存取次数：

数据结构实际应用中，涉及磁盘等外部存储设备的读写（系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是想要什么取什么）。而磁盘的读写是十分耗时的。所以，减少磁盘读写（存取）的次数，是各种数据结构面临的挑战！

B-Tree与AVLTree对比：递归二叉树变为范围逐步锁定，树的深度越矮胖，磁盘存取次数越少。

以MySql为例，InnoDB存储引擎中有页（Page，磁盘管理的最小单位，默认大小为16KB（可修改），可以通过`show variables like 'innodb_page_size';`语句查看对应值）的概念。InnoDB在把磁盘数据读入到内存时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。设定B-Tree每个结点占用一个盘块的磁盘空间，与AVLTree相比，缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。平衡二叉树是通过旋转来保持平衡的，而旋转是对整棵树的操作，若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n（底数为2），这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理），所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。小结：降低树的深度意味着树更宽（更矮胖型），内存每次加载的磁盘数据索引的信息量越大，意味着每次磁盘存取获取的信息量越广，后续需要继续深度探寻树的索引信息的必要性会减弱。在加载内存的层面理解，树越矮胖，单个结点索引信息密度越高，一次加载到内存的索引信息就越广，整体磁盘存取次数更少。

B-Tree与B+Tree对比：B+Tree一次载入磁盘的索引信息越多，磁盘存取次数越少。

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。（树的深度更低，因为B+Tree非叶子结点是纯粹的索引，同一个磁盘块可以放置更多的索引信息，加载到内存相当于一次获取的可搜索定位的范围更广，所以磁盘存取次数更少）由于B树的节点都存了key和data，而B+树只有叶子节点存data，非叶子节点都只是索引值，没有实际的数据，这就时B+树在一次IO里面，能读出的索引值更多。从而减少查询时候需要的IO次数！

什么是LSM？

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

为什么需要LSM？

答：B树及相关变种，可能逻辑上很近但物理上很远，会导致大量磁盘随机读写，时间性能不佳。LSM能让我们顺序写磁盘。

LSM如何实现顺序写？

答：要理解LSM的数据结构。LSM的数据结构由两个或以上的存储结构组成。

举例：

一个C0 Tree（在memory中）：可以是任何方便键值查找的数据结构（比如：红黑树、Map或者跳表）另一个C1 Tree（在Disk中）：类似B树。C1所有结点都是100%满的，结点大小为磁盘块大小。- 插入步骤：  1. 插入一条新纪录，首先在日志文件中插入操作日志（可以后续恢复）。操作日志以Append方式插入（快）。  2. 将新纪录的索引插入到C0中，此处在内存中完成，不涉及磁盘操作（快）。  3. 当C0达到某一阈值或者隔一段时间，将C0记录滚动合并到C1。  4. 当有多个存储结构时，C1再滚动合并到C2，C2再滚动合并到C3，以此类推到Ck。- 合并步骤：涉及两个块（emptying block和filling block）  1. 将C1中未合并叶子节点放置内存中的emptying block中。  2. 从小到大找C0中的节点，与emptying block进行合并排序。合并结果保存到filling block中，同时将C0对应节点删除。  3. 不断执行1和2的步骤，合并结果不断填入filling block中，当其满了则将其追加到磁盘的新位置上。（注意是追加不是改变原有节点）  4. 合并过程中，如果使用完了，则再从C1中读取未合并的叶子节点。  5. C0和C1所有叶子节点都按以上合并完成后即完成一次合并。  6. 备注：emptying block可以理解为是C1要进行合并的叶子节点的缓存，filling block可以理解为是合并结果的固定大小（磁盘块大小）的缓存。（类比固定大小集装箱不断追加到磁盘的新位置上）- 查找步骤：  1. 先找内存的C0树，找不到则找磁盘的C1树，然后是C2树，以此类推。- 删除操作：  1. 通过标记来实现，在内存中将要删除的记录标记一下，后面异步执行合并时将相应记录删除。  2. 而如果C0树不存在的记录，则在C0树中生成一个节点，并标为#，查找时就能在内存中得知该记录已被删除，无需去磁盘找了。比如要删除“B”，那么没有必要去磁盘执行删除操作，直接在C0树中插入一个“B”节点，并标为#。

LSM有哪些优化策略？

1. 布隆过滤器快速判断Key是否存在。2. 额外索引快速找到记录。3. 开启WAL日志提升写性能。4. 提升读性能。   4.1 二分查找：将文件数据有序保存，使用二分查找来完成特定key的查找。   4.2 哈希：用哈希将数据分割为不同的bucket。   4.3 B+树：使用B+树 或者 ISAM 等方法，可以减少外部文件的读取。   4.4 外部文件：将数据保存为日志，并创建一个hash或者查找树映射相应的文件。

如何理解WAL？

rollback journal机制：在修改数据库文件中的数据之前，先将修改所在分页中的数据备份在另外一个地方，然后才将修改写入到数据库文件中；如果事务失败，则将备份数据拷贝回来，撤销修改；如果事务成功，则删除备份数据，提交修改。
- 修改前先备份，失败可以复原。成功，则删除备份。
修改并不直接写入到数据库文件中，而是写入到另外一个称为WAL的文件中；如果事务失败，WAL中的记录会被忽略，撤销修改；如果事务成功，它将在随后的某个时间被写回到数据库文件中，提交修改。
- 写到WAL文件记录操作，事务成功，则后续同步数据库文件。
同步WAL文件和数据库文件的行为被称为checkpoint（检查点），它由SQLite自动执行，默认是在WAL文件积累到1000页修改的时候；当然，在适当的时候，也可以手动执行checkpoint，SQLite提供了相关的接口。执行checkpoint之后，WAL文件会被清空。
- 同步WAL文件和数据库文件的行为被称为checkpoint（检查点）
在读的时候，SQLite将在WAL文件中搜索，找到最后一个写入点，记住它，并忽略在此之后的写入点（这保证了读写和读读可以并行执行）；随后，它确定所要读的数据所在页是否在WAL文件中，如果在，则读WAL文件中的数据，如果不在，则直接读数据库文件中的数据。
- 读之前确定写入点，先读写入点之前的WAL文件，没有再读数据库文件。
在写的时候，SQLite将之写入到WAL文件中即可，但是必须保证独占写入，因此写写之间不能并行执行。开启WAL模式可以提高写入数据库的速度，读和写之间不会阻塞，但是写与写之间依然是阻塞的。在项目中开启WAL模式，可以提高并发。由于使用WAL比rollback journal的模式减少了写的i/o，所以写入时速度较快，但是由于在读取数据时也需要读取WAL日志验证数据的正确性，所以读取数据相对要慢。
- WAL文件写独占，减少了写的i/o，增加了读取WAL日志验证数据的正确性。
思想：增量修改在内存中（减少IO时间）。基于硬盘的数据结构，批量写入到磁盘（减少磁盘时间）。

参考文章：

https://blog.csdn.net/weixin_33946020/article/details/87951511（WAL）
https://blog.csdn.net/las723/article/details/93767240（LSM）
https://baijiahao.baidu.com/s?id=1675908267465133255&wfr=spider&for=pc（跳表）
https://www.cnblogs.com/lfri/p/9991925.html（SkipList的基本原理）
https://blog.csdn.net/kuang5683608/article/details/6333693（动态查找树比较）
https://blog.csdn.net/xiaojin21cen/article/details/97602146（数据结构 —— 图解AVL树(平衡二叉树)）
https://www.cnblogs.com/skywang12345/p/3245399.html（红黑树(一)之原理和算法详细介绍）
https://download.csdn.net/download/gzharryanonymous/10456354（普林斯顿大学算法公开课：平衡搜索树）
https://www.cnblogs.com/rcpalc/p/4055709.html（红黑树的时间复杂度为: O(lgn)）
https://blog.csdn.net/CreationAugust/article/details/41519181（【平衡二叉树】SBT学习笔记）
https://blog.csdn.net/murmured/article/details/17029131（Size Balanced Tree(SBT树)整理）
https://wenku.baidu.com/view/8c944c8fcc22bcd126ff0c7b.html（陈启峰Size_Balanced_Tree中文修正版）
https://baike.baidu.com/item/Treap/4321536?fr=aladdin（Treap）
https://blog.csdn.net/xipitu/article/details/81545346（数据结构：伸展树Splay）
https://www.cnblogs.com/2018zxy/p/10055335.html（伸展树）
https://blog.csdn.net/xiaojin21cen/article/details/99868841（数据结构 —— B*树）
https://www.jianshu.com/p/ace3cd6526c4（B+树和B树的区别）
https://www.jianshu.com/p/3fb899684392（LSM、B 树、B+树、B*对比）
https://blog.csdn.net/ws1296931325/article/details/86614525（平衡多路查找树（B-Tree））