红黑树、B树、B+树和跳表

一、内存存储

1 红黑树

首先来看看红黑树目前的应用：

• JDK1.8中HashMap引入的红黑树——当链表长度超过8，且数组长度超过64时，将会将链表转为红黑树
• epoll注册、监听socket事件采用的数据结构是红黑树

1.1 二叉查找树到二叉平衡树

二叉查找树的定义——左子树中的所有节点的值小于等于根节点的值，右子树中的所有节点的值大于等于根节点的值。

对于BST来说，还有一个比较有意思的性质——中序遍历得到的结果乃是升序序列

对于二叉查找树的插入操作来说，我们可以很简单地用以下伪代码来表示：

def insert(root, val) -> TreeNode:
    if root == None:
        return TreeNode(val)
    if root.val == val:
        tmp = root.right
        root.right = val
        node.right = tmp
    elif root.val < val:
        root.right = insert(root.right, val)
    elif root.val > val:
        root.left = insert(root.left, val)
    return root

对于二叉查找树的插入操作将导致一种极端情况——如果接下来插入的值呈现升序现象，那么二叉树将会退化成一条链表。此时查询的时间复杂度俨然来到了O(n)。

故为了防止这种情况发生，我们需要对二叉树进行平衡操作，即通过旋转节点，来降低左右子树的高度之差。

平衡二叉树最重要的性质就是每个节点的左右节点高度之差最多为1

接下来看看是如何进行平衡操作：

1. 找到失衡节点，从刚得出的性质我们可以知道所谓的失衡节点就是左右节点高度之差大于1的节点
2. 找到旋转支点，此时就需要根据具体的失衡场景进行区分

LL即左子点的左节点，RL即右节点的左节点，RR、LR同理 旋转支点只会出现在失衡节点的子节点、孙子节点中

• 对于LL、RR失衡，那么旋转支点就是LL中的第一个L、RR中的第一个R。此时根据该支点，将失衡节点下旋（右旋/顺时针旋转、左旋/逆时针旋转）即可
• 对于LR、RL失衡，那么旋转支点就是LR中的R、RL中的L。此时根据该支点，先将支点的父节点下旋，再将失衡节点下旋

而由于避免了二叉树退化未链表的极端情况，故可以保持查询时间复杂度在O(logn)。

但是由于每次操作平衡树时都需要保证左右子树的高度之差，那么在具有频繁修改行为的场景下将表现出较差的性能。因此红黑树就诞生了，它放宽了树的平衡条件，从而在查询和修改中都取得较为不错的性能。

正所谓软件开发的过程中都是权衡利弊嘛，没有最好的，只有最合适的^^

1.2 认识红黑树

首先看看红黑树的特性，同时也是平衡的条件：

1. 根节点、叶子节点的左右节点（可以视作null节点）是黑色
2. 每个红色节点的两个子节点都是黑色
3. 任一节点到叶子节点的所有路径中，黑色节点的数目是一样的

接下来简单看看是如何进行平衡操作：

1. 变色

• 对于插入操作来说，插入的节点都初始化为红色，因为父节点为黑色的概率比较大，从而可以避免颜色冲突而导致变色操作

2. 左右旋（和平衡树差不多）

• 任何不平衡都会在三次旋转之内解决。平衡树的递归旋转操作转变为了递归变色操作，而变色操作的效率是比旋转要好一些的，因为少了很多移动指针的操作。

2 代替树的结构——跳表

首先来看看跳表的应用场景：

• Redis的Zset有序集合
• 大部分采用LSM Tree作为存储引擎的应用都倾向于使用跳表作为内存中的数据结构，例如LevelDB、RocksDB

2.1 认识跳表

所谓的跳表实际上就是通过增加索引，从而实现二分查询的效果。在跳表中的每一个节点中，我们可以认为有以下属性：

• data保存数据
• next指向同级索引的下一个节点或者原始节点的下一个节点
• down指向上级索引节点或者原始节点

如果需要固定每一层索引的数量和间距的话，那么就将导致每次插入节点时，都需要对索引进行重建。但如此一来将会使得每次插入都是O(n)的时间复杂度。

故我们可以退而求其次，让每一层的索引数量保持不变，但是间距将会随机化。

• 插入时，根据概率算法来得出需要添加哪些层的索引节点。
• 其中这个概率算法需要控制有1/2的概率返回1，1/4的概率返回2，1/8的概率返回3，后续更高层的索引以此类推。
• 对于如果该概率算法返回的是1，那么表明直接在原始链表上添加节点即可；如果返回的是2，那么表明不仅需要在原始链表上添加节点，而且需要创建一级索引，后续返回值以此类推。
• 故最终可以实现一级索引有n/2个节点，二级索引有n/4个节点，后续更高层的索引以此类推。
• 最终插入的时间复杂度为O(logn)
• 删除时，由于也需要将索引节点删去，故时间复杂度也为O(logn)

3 跳表和红黑树的应用场景

• 跳表的实现相对简单，利用代码的维护
• 查询和修改的时间复杂度都属于O(logn)，适合大部分读写频繁的场景。但实际上由于跳表的插入依赖于概率算法，故极端情况下时间复杂度可能会退化为O(n)
• 跳表的空间复杂度需要额外的O(n)来存储索引节点，而对于红黑树来说也可以视作需要额外的O(n)，但是仅仅需要在每个节点存储颜色状态即可。故前者的空间可能会耗费更多一些
• 跳表的并行度会比红黑树要高。各索引层之间的操作较为独立，减少了线程间的冲突。而红黑树由于需要维持平衡特性，故多线程环境下较为复杂。
• 仅适合于内存中使用，而不适合作为外部存储的数据结构，因为各种操作都是依托于指针的跳跃移动，如果查询数据分散在不同的磁盘块，那么将导致多次的磁盘读写，这将会导致性能急速下降。

此时链表优化为具有类似于树状结构的跳表来说，实际上反而成为它低效的原因。但反过来说，如果没有这种树状结构，那么即使在内存这种随机存储的介质中也无法赋予链表高效的查询效率。

二、外部存储

1 B树和B+树

1.1 磁盘读写

尽管在内存中红黑树和跳表能够提供非常不错的效率，但是到了磁盘上就不是那么一回事了，所以需要B树这种多路搜索树。

B树通过降低树的高度，避免了大量数据分散存储，进而减少指针跳跃，即减少了磁盘读写的次数。除此之外，B树每个节点存储数据时，采用的是数组而不是链表，如此一来就可以保证每个节点的数据都是顺序写入。

而B+树则是根据磁盘读写的特性做了更进一步地优化：

• 非叶子节点不存储数据，那么一个磁盘块中可以存储的非叶子节点就更多了，也就相当叶子节点数量可以更多了。同时最关键的是——这将不会让树的高度增加，故并不会降低磁盘读写效率。
• 叶子节点通过指针相连，在区间查询的操作中，就可以避免返回父结点所在的磁盘块去寻找另下一个叶子节点所在磁盘块的情况，即减少1次磁盘读写

需要注意的是，对于MySQL来说，B+树高度一般在三层。当数据量到达千万级时性能将会下降。而《阿里巴巴Java开发手册》中提到，单表超五百万就应该分表了。

1.2 内存管理

1.2.1 操作系统的内存管理

对于操作系统来说，磁盘空间管理是以块为单位的，磁盘块的大小一般来说是512KB；内存空间管理是以页为单位的，页的大小一般是4KB，实际上还可以在操作系统层面开启大内存分页，一般来说是2048KB大小的页。

sudo sysctl -w vm.nr_hugepages=2048 # 允许应用使用最多 2048 个大内存页。
grep Huge /proc/meminfo # 可以查看服务器大内存页的使用情况

什么情况下需要使用大内存分页？ 首先我们要知道CPU的指令周期中fetch、execute和store这三个步骤都有可能发生内存的存取操作。但是内存的访存则达到了200-300个时钟周期。这样的速度差异意味着每次执行一条指令都可能需要多耗费数百个时钟周期去从页表中找到对应的页地址，这是令人难以接受的。 很自然我们可以想到将页表缓存到离页表更近的地方，例如L1/L2/L3。最终为了更好的加速页表访问，我们选择在CPU中使用专门的寄存器TLB来缓存页表，此时访问TLB和访问L1的时间相当，如此一来就可以节省地址转换的时间了。（实际上，L1被划分为两块区域，分别是指令区和数据区，如果再划分出一个页表区，反而增加了L1的复杂性，倒不如专门增加一种寄存器来缓存。） 现在我们引入了TLB，此时终于到了我们的重点，为什么要使用大内存分页？简单来看，页表就是虚拟地址到物理地址的一个键值对。 我们假设物理内存大小为4G，那么对于4KB的页来说，那么就存在4G/4KB=4M个页面，即页表共有4M项条目，而4G的内存大小即存在0-2^32-1的地址范围，页表每一项的最小大小就是4B，故页表大小为4B*4M=16MB。（当然实际来说可能会采用多级页表进行地址管理） 那么对于大内存分页来说呢？例如2048KB的页，那么此时就存在4G/2048KB=2K个页面，最终可得页表大小为4B*2K=8KB。 显而易见，使用大内存页，使得我们的页表大大减少，那么此时TLB可缓存的页表数量也就大大增加，故可以避免在内存密集操作的场景下，页表不断的换出导致的缓存命中率下降。除此之外，大内存页可以避免内存碎片过多的问题，从而提升内存利用率。

一般来说，如果应用层不是自缓存（直接IO）的话，那么我们在读取磁盘的某些数据时，都会利用PageCache（缓存大小一般是页大小的整数倍）将整个磁盘块的数据缓存到内存当中存储，这种预读数据和缓存最近被访问的数据可以有效地提高读写效率。

• 读是指可以直接读缓存中的数据
• 写是指累计一批写入再统一刷盘到磁盘上

1.2.1 InnoDB的内存管理

对于MySQL来说，是基于16KB的页作为最小的读写单元来操作数据，故每次读写一个页，实际上对应了操作系统的4个页。对应地，如果操作系统开启了大内存分页，那么MySQL也可以开启大内存分页机制。

为什么要Double Write Buffer？ 前面提到，InnoDB读写一个页实际上对应着操作系统的4个页。如果考虑到InnoDB页写入操作系统页时，突然宕机了，那么可能会出现部分页数据未修改的情况。 我们下意识地认为redo日志将会将此次崩溃事务数据进行恢复，但是实际上，redo日志属于WAL预写日志，记录的数据乃是真实写入物理磁盘的日志。而上述问题实际上是针对未写入的那部分数据应该如何补偿。 故InnoDB采用了Double Write Buffer来解决这个问题。实际上InnoDB是通过redo日志和Double Write Buffer来共同实现数据一致性。 首先要知道该机制中，内存存在一个double write buffer，用于接收将要修改的InnoDB页；在磁盘中也存在一个double write区域（属于共享表空间），用于持久化double write buffer中的InnoDB页。 该机制在将InnoDB页数据写入到操作系统页之前，先将InnoDB页备份下来，即InnoDB页复制到double write buffer，再顺序写入double write。在将InnoDB页数据写入到操作系统页之后，就会将操作写入redo log buffer，当事务提交后再顺序写入磁盘。 当事务提交后，InnoDB页未刷盘成功时，就会触发redo日志恢复事务。后续如果有需要，即当部分页未写入问题时，则通过double write找到备份的InnoDB页进行恢复。

除此之外。InnoDB存储引擎还自建了一套缓存机制，即Buffer Pool，默认是128M。这套缓存机制默认使用的缓存IO，磁盘数据实际上先缓存到PageCache中，然后再读取到Buffer Pool。但MySQL还提供了另一种可选方式，即开启直接IO，此时MySQL将直接在用户空间层面读取磁盘数据，而不需要经过内核空间的PageCache。

2 外部存储——哈希索引

• 内存中将要维护一个哈希表来访问磁盘，K-V1键值对，V1即原始K-V0在磁盘上的偏移量。磁盘上将会将数据以原始的K-V0进行存储，V0是K的记录值而不是偏移量
• 只会顺序追加写入磁盘，对于读取以最新数据为准
• 哈希表存储在内存中，能迅速定位磁盘位置，故读写十分的快。但由于需要在内存中维护哈希表，可能会占据大量内存空间
• 数据分段，当追加入磁盘的数据超出一定大小后，将会开启另一个新文件来存储数据。旧文件可以进行压缩（这里将会涉及到rehash），此时旧文件的哈希表一般不会再变动，故可以进行持久化，当崩溃时加速哈希表的重建。当文件过多时，可以进行文件合并。
• 无序，不支持范围查询，一般只适合键值存储的场景

3 外部存储——SSTable以及LSM

SSTable就是排序字符串表：

• 字符串：对于每条记录/每个元素都是基于K-V的字符串。
• 表：存储多个元素的数据结构就是线性表
• 排序：表存储元素的次序是根据元素中的K来决定的

基于合并和压缩排序文件原理的存储引擎一般都可以称之为LSM存储引擎。

1. 首先写入操作将会写入内存中的memtable（数据结构可以是红黑树、跳表）

• 为了防止数据丢失，还会使用WAL预写日志保证数据可靠性
• 当memtable超过一定的大小之后，就会转变为immutable memtable，然后异步持久化为SSTable文件。同时会在内存中新建一个memtable，用于接收新的写入操作。

2. 为了加速查找磁盘中的数据，会在内存中维护一个布隆过滤器和稀疏索引

• 稀疏索引就是哈希表，其中K-V1中的V1是K在磁盘上的偏移量。通过稀疏索引可以定位K可能在磁盘上的偏移量范围
• 布隆过滤器主要是为了解决K不存在磁盘中的问题。稀疏索引并不能判断K是否存在于磁盘中，故无论存在与否都得进行一次磁盘访问。引入布隆过滤器之后，就可以快速判断K是否存在于磁盘上了，从而避免磁盘访问。

3. 当磁盘存储的SSTable文件超过一定数量后，便会进行合并操作，真正地删除冗余K，从而压缩磁盘空间。压缩之后所有SSTable文件呈现多级结构。之所以这样做，则也考虑到了局部性原理事实，此时认为越深的层级，那么访问的概率将会十分低。一般来说有以下两种压缩策略：

• size-tiered compaction(大小分级压缩)：每层规定SSTable文件的最大数量，当超出该阈值时，将会合并该层所有的SSTable文件放入下一层中。
• 需要注意的是，在执行压缩完成之前，该层的所有SSTable都不能被删除，那么就有可能出现空间放大的毛刺现象，并且极端情况下（SSTable文件中的Key都没有重复）空间将会放大到原来的两倍。
• 而由于压缩可以视作是增量进行的（当该层超过SSTable文件数量阈值时才会压缩），那么同层级的SSTable文件中出现冗余Key是不能及时压缩消除的，此时还是会出现空间放大的问题。
• leveled compaction(分层压缩)：同层级的SSTable文件中包含不同范围的Key，即保证了同层级的Key不会出现冗余的现象。对于从内存到磁盘的最新SSTable来说，我们称该层为level 0，该层不需要有此规定。
• 当某层的数据量大小超过阈值时，将会选择该层的SSTable文件、根据Key压缩至下层SSTable文件中。虽然解决了空间放大问题，但是却出现了严重写放大的问题。对于同一份Key来说，在逐步压缩至下层SSTable的过程中最终会出现写入n次的情况。

空间放大即存储引擎中占用的磁盘空间大小比有效数据大小要偏多的现象。例如有效数据是1MB，而由于有效数据冗余导致实际磁盘空间大小为2MB。对于HDD来说，解决空间放大问题的优先级高于写放大，或者说，在使用HDD的前提下，写放大并不存在很致命的问题。 写放大即向磁盘写入的数据量比有效数据大小要偏多的现象。例如有效数据是1MB，而由于有效数据重复写入导致实际磁盘写入量为2MB。对于SSD来说，解决写放大问题的优先级高于空间放大，因为对于SSD来说，每次写入都需要先擦除数据，而SSD的擦除次数是有限的。

LSM和B+树的区别

1. 由于数据都是顺序写入的，故提高了写入能力。但是由于数据很容易分散在各个SSTable中，故牺牲了读取的性能。但也可以通过稀疏索引、布隆过滤器来避免多余的磁盘访问才能定位到所需数据。
2. 由于SSTable文件属于追加式以及不可变的，那么就不会出现B+树这种原地更新的方式出现部分旧值的问题——在崩溃时，同一事务的多个写操作可能仅有一部分内容真正写入磁盘。为了防止这种情况的发生，InndoDB就采取了redo、double write等等机制来解决这个问题。

三、数据恢复的手段——日志

日志一般是顺序写入的，故可以尽可能地加速每次写入后立即刷盘的速度（如果为了更进一步地加速，可能还是会使用缓冲区来异步批量地将日志写入磁盘）。

一般有以下三种形式的日志：

1. 预写日志，顺序写入写操作。预写日志操作的数据十分底层，将会记录具体操作到了哪个磁盘块的哪些字节。
2. 基于操作语句的日志，顺序写入每种操作语句。更偏向于应用层面。但对于一些特殊的函数将可能无法正确的还原数据
3. 基于行的日志，顺序写入每一行的数据。更偏向于应用层面。 对于基于内存的存储引擎来说，可能只需要写入基于语句、基于行

四、基于内存和基于磁盘的存储引擎效率差在哪里？

基于内存的存储引擎相比于基于磁盘的存储引擎来说，之所以前者效率更高，那是因为前者不需要对内存的数据结构进行复杂的编解码。实际上基于磁盘的操作最终都需要将数据从磁盘取到内存中来进行操作。

• 对于存储引擎来说，不想每次写操作都立即写入磁盘，因为这种独立的写入将会造成每次IO操作都出现较长的寻道和旋转。而通过缓存写操作，最后统一写入，则既可以避免多次IO请求，也可以尽可能地缩短寻道和旋转地整体时长。
• 但是一旦介入缓存，那么就必然会出现数据丢失的问题，此时基本上都会通过WAL预写日志来解决这个问题——即及时地将写操作顺序的写入磁盘。
• 如此一来我们便将最开始的n次写操作+n次随机寻道和旋转转变为n次写操作+n次顺序写入+1次写操作+1次尽可能短的随机寻道和旋转。虽然IO请求的次数多了，但是由于尽可能地顺序写入，所以整体上的写入效率将会大大的提升。

作者：hhuang1231

链接：
https://juejin.cn/post/7388057629775085594

#记录我的2024#