database shit -RAM structure

到了主攻了

存储结构的分类

in place update: 就地更新结构，如B和B+树，直接覆盖旧的记录来存储更新内容，读的性能更高

out of place update: 异位更新结构，如LSM tree，新的内容存储到新的位置，而不是覆盖老的结构，由于是顺序写，写入性能更高

SSD因为随机读减少了寻道时间，LSM对SSD上的写更加友好

存储结构的共性：

1.适合磁盘存储

2.允许并发操作：对B树来说，需要锁上所有有问题的节点（SMO操作）

两种不同的控制并发的锁

lock是逻辑锁，latch是物理锁

我们知道，目前主流的sql数据库采用的是B+tree的结构,Nosql大多采用LSM tree，今天先把这三种结构说一哈

B tree & B+ tree

B tree

首先，我们得清楚，对于数据库系统来说，最重要的地方就是要减少磁盘IO，因为很慢！
那么Btree有些什么性质呢？

1.高度为O(logn)但是常数小很多

2.一个节点的大小和磁盘页的大小相当，根节点一直保存在主存中

3.一次读取造成logn -1次磁盘读取

4.对于t-1阶的b tree来说，每个节点的孩子节点数量在[t,2t],所以key的数量在[t-1,2t-1]

5.对于一颗b树来说，高度为${height<=log_{t}(n+1)/2}$

B tree的操作

1.查找

很简单，每个节点遍历一下就好了

2.插入

分为以下几步

1.查看当前根节点的key数量是否为2*t-1,如果是转2，不是转5

2.创建新节点，让新的空节点为根，转到3

3.新节点插入根节点，转到4

4.把根节点分裂，分成两份，转到5

5.该节点是否为叶结点，是转6，不是转7

6.二分找到适合的位置，插入

7.是否到达2k-1？是的话分裂，不是继续转5

3.删除

先给出一个前提，我们只在有t个key的时候进行删除

分为以下几种情况

1.直接删除叶子，叶子也可以删（t）

直接删了就好了

2.删除内部节点，左孩子有t个key

把左孩子里最大的移动到删除位置即可

3.删除内部节点，右孩子有t个key

把右孩子最小的移动到删除位置即可

4.删除内部节点，两个孩子都只有t-1个key

把内部节点和右孩子都移动到左孩子中，现在有2t-1个key，那么我们直接删除对应节点

5.删除某节点，但是其父亲节点只有t-1个key

把父亲节点的兄弟节点移动到靠左的节点中（父亲或者兄弟），然后把爷爷节点移动到靠左的节点中，然后再删除对应的节点

6.删除某节点，某节点只有t-1个key，兄弟节点右t个key
把父亲节点的值移动到删除位置，把兄弟节点的最小值移动到父亲节点

和B+树的区别

1.B树的每个节点都存储了key和data，而B+树的data存储在叶子节点上。
B+树非叶子节点仅存储key不存储data，这样一个节点就可以存储更多的key。可以使得B+树相对B树来说更矮（IO次数就是树的高度），所以与磁盘交换的IO操作次数更少。

2.B+树所有叶子节点构成一个有序链表，按主键排序来遍历全部记录，能更好支持范围查找。
由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

3.B+树所有的查询都要从根节点查找到叶子节点，查询性能更稳定；而B树，每个节点都可能查找到数据，需要在叶子节点和内部节点不停的往返移动，所以不稳定。

LSM tree

写入过程：
1.首先记录write ahead log (类似redo log)

2.有序写入active memtable(结构为redis的跳表，这是唯一可变的结构)

3.active memtable写满了之后转换为immutable memtable.

4.immutable达到指定数量后，将其落盘到磁盘的L0层，这步操作也叫minor merge,通常对这一步操作直接落盘，所以L0层可能有重复数据

5.L0层满了之后，会出发关键的major merge操作，也就是compaction,把L0和L
进行合并，称之为SSTable，就是一个小型的聚簇索引，这个结构整体不可变（跳表存索引）

6.compaction向下合并的过程中碰到同key数据，那么就合并，如果遇到更高层的新的数据，那么就被覆盖

7.读取的过程就是从上到下，一层一层扫描，可以使用布隆过滤器(对每个key做哈希，做成一个bit数组)加速扫描，用来筛选该层中是否包含我们要查找的数据，可能返回假阳性结果，多个哈希函数

不同的合并策略：

leveling merge:每次把该层和下一层进行合并

tiering merge，每次把当层相邻合并，并写入下一层

并发：
1.memtable 落盘操作

2.compaction过程

优化方案：
1.流水线技术，把读取，合并，写入三个操作以流水线形式执行

2.复用组件，在合并的过程中识别出不变的部分并且保留

3.在compaction结束后主动更新cache

4.单独硬件执行Compaction

LSM tree的索引

在LSM Tree的顶层，通常使用内存中的数据结构，如B+树或哈希表等来实现索引。这些数据结构可以快速响应读写操作，适合处理频繁访问的数据。

在LSM Tree的底层，通常使用SSTable（Sorted String Table）或者类似的数据结构来存储索引。SSTable将数据按照key排序并存储在文件中，同时维护一个索引文件，可以支持快速的查找和范围查询操作。SSTable中的索引通常是基于Bloom Filter(每个SSTable可以对应一个布隆过滤器，该过滤器存储了SSTable中所有键的哈希值，以及一些用于计算哈希值的参数。在查询时，先将查询键的哈希值通过布隆过滤器计算出多个位置，如果这些位置都为1，则说明查询键可能存在于该SSTable中，否则肯定不存在于该SSTable中。

)或者Skip List等数据结构实现的。

LSM tree的compaction

合并成一个新的SSTable，并将其中的重复记录合并，并按照键的有序性进行排序，最终将其写入一个新的文件中。通过Compaction操作，可以将多个小的SSTable合并成一个大的SSTable，从而提高查询效率，同时也可以释放磁盘空间，避免数据的冗余存储。

LSM tree的数据恢复

一般来说，LSM树中的数据恢复可以分为两个阶段：恢复元数据和恢复数据。

恢复元数据：当LSM树中的某个SSTable文件损坏或丢失时，需要先恢复该文件的元数据信息，以便后续能够正确地读取和处理数据。元数据信息通常包括SSTable文件的基本信息、索引信息和数据块的位置信息等。

恢复数据：恢复数据的过程需要读取多个SSTable文件，并将它们合并成一个新的SSTable文件。在合并的过程中，需要按照键的有序性进行排序，并去除重复的记录，最终生成一个新的SSTable文件。在生成新的SSTable文件之后，还需要将其合并到LSM树中，以确保LSM树中的数据是完整的。

需要注意的是，在LSM树中，由于数据是分层存储的，因此在进行数据恢复时，需要从底层的SSTable文件开始读取数据，并逐层向上进行合并。

LSM tree的合并策略

LSM tree异步的写操作

在LSM树中，写操作是通过将数据追加到内存中的数据结构中来实现的，这个过程通常是异步的。异步写操作的具体实现方式会因不同的LSM树实现而有所不同，一般有以下几种方式：

1.使用后台线程：LSM树通常会使用专门的后台线程来将内存中的数据异步写入到磁盘上的SSTable文件中。后台线程会不断地将内存中的数据写入到磁盘上的SSTable文件中，直到所有数据都被写入为止。

2.使用内存映射文件：LSM树可以将磁盘上的SSTable文件通过内存映射的方式加载到内存中，然后直接向内存映射文件写入数据。由于内存映射文件的写入操作会自动触发操作系统将数据写入到磁盘上，因此不需要显式地进行写入操作。

3.使用缓冲区：LSM树可以使用一个缓冲区来缓存待写入的数据，当缓冲区中的数据达到一定大小或时间间隔时，才将缓冲区中的数据写入到磁盘上的SSTable文件中。这种方式可以减少磁盘写入操作的次数，提高写入性能。

无论使用哪种方式，LSM树都可以通过异步写入操作来提高写入性能和并发能力。

LSM tree的删除操作

在LSM Tree中，删除操作不会直接删除磁盘上的数据，而是通过增加一个特殊标记来标记键值对已经被删除。在LSM Tree中，一般使用一种被称为“tombstone”的特殊标记来标记删除的键值对。
假设现在有一个LSM Tree，其中包含如下键值对：

{1: "A"}, {2: "B"}, {3: "C"}, {4: "D"}, {5: "E"}

现在要删除键为2的键值对，那么LSM Tree会把如下的删除操作写入WAL：

DEL 2

这样就标记了键为2的键值对已经被删除。当WAL被写满后，LSM Tree会进行压缩操作，把键为2的键值对从内存中的层中删除，并将其合并到磁盘中的更高层。在合并过程中，LSM Tree会使用tombstone标记已经被删除的键值对。

LSM tree的WAL

LSM树的WAL（Write-Ahead-Log）主要用于数据持久化，即在数据写入磁盘之前先写入WAL中，以便在系统崩溃时可以恢复数据。

下面是一个简单的例子，说明LSM树的WAL可能包含哪些信息：

假设有一个包含3个层级的LSM树，其中每个层级都有两个SSTable（Sorted String Table），每个SSTable包含3个键值对（K-V）。

在向LSM树中插入一个新的K-V之前，需要将该K-V写入WAL中。此时，WAL会记录以下信息：

插入操作的类型（Insert）；
K-V的键值；
K-V的值；
操作的时间戳。
假设要插入键值对（K1,V1），那么在WAL中记录的信息可能如下所示：

Insert,K1,V1,timestamp1

做merge的时候也会写WAL

Merge,timestamp2,timestamp3,new_SSTable,K1-K3@SSTable1,K4-K6@SSTable2,timestamp1,timestamp2,timestamp3,timestamp1,timestamp2,timestamp3