数据库原理 LSM vs BTree

数据库的本质就是帮助我们存储和获取数据个中间件。最简单的数据库可以通过下面两个脚本实现。

[qa@qaserver1 db]$cat set.sh
#!/bin/bash

echo "$1,$2" >> database

[qa@qaserver1 db]$cat get.sh
#!/bin/bash

cat database | grep "$1," | tail -n 1 | awk -F, '{print $2}'

这个实现写入十分高效，所有的写入都是顺序写入，查询性能就比较糟糕，时间复杂度O(n)，每次都是全部扫描。

数据库设计者们通过修改数据的存储结构，或者在数据外额外的维护一份元数据来加速查询过程，这一份额外的元数据被称为索引，最常见的索引是Hash索引、LSM-Tree、 B+Tree。

以我们上面举例的最简单Key-Value数据库为例，最直观的索引结构就是Hash索引，在内存中维护一个HashMap，HashMap的Key就是数据库的Key， HashMap的Value是文件内位置(offset)。

image.png

有了Hash索引后，每次我们可以通Key找到记录地址，seek到特定位置，直接读取数据返回。每次写入数据时，需要同时更新Hash索引。

Hash索引有两个明显的缺陷:

数据文件如果只是不断的追加，即使数据库系统不间断正常运行，文件会越来越大，文件里的无用信息越来越多(一个Key的值修改了N次，文件里记录了N条，只有最后一条有意义)，如果从文件从新构建索引，耗时也会很长。

于是数据库设计者们想到了将数据文件切分，切分的每一段被称为一个Segment，只有当前Segment会有数据Append动作，历史Segment都可以认为是固定的。

那我们就可以启动后台线程对历史Segment做合并压缩(Compaction)，一个Key的多次操作只保留最后一条，之前已经标记为删除的数据移除。

image.png

每个Segment都有对应的Hash索引，查找特定Key时，我们需要依次查询Segment对应的Hash索引。

这类存储引擎称为 Append-Only Log-Structed。它们的优点是:

确定也很明显:

前面提到用Hash索引是需要将每个Key保存到内存中，但是内存可能无法放下所有的Key。 SSTable完美解决了这个问题， SSTable全称Sorted String Table，要求每个Merged-Segment里Key只出现一次，且Segment内Key是有序的。

相比之前简单的拆分Segment，SSTable有如下优势:

那如何做到Segment内部有序呢？因为数据写入会先经过内存，我们可以在内存维护一个红黑树(Red-Black Tree)或者平衡二叉树(AVL Tree)。

写入SSTable的工作流程:

读取SSTable的工作流程:

==LSM-Tree的三大核心主键就是: Write-Ahead-Log、 Memtable 、 SSTable，上面我们讲的其实就是LSM-Tree的核心思想。==

LSM-Tree已经被广泛使用，如LevelDB、 RocksDB、 Cassandra 、 HBase都采用这个核心架构。 SSTable的概念也被广泛借鉴，如ClickHouse、 Palo里都有相关概念。

LSM-Tree的优点：

LSM-Tree的缺点：