# minidb

**Repository Path**: motor_2/minidb

## Basic Information

- **Project Name**: minidb
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-11-19
- **Last Updated**: 2024-11-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


https://blog.csdn.net/qq_33339479/article/details/119645738

https://mp.weixin.qq.com/s/kCpV0evSuISET7wGyB9Efg

LSM树（Log-Structured Merge Tree）和SSTable（Sorted String Table）之间的关系是紧密且互补的。LSM树是一种数据结构，它通过优化写入操作来提升性能，而SSTable是LSM树在磁盘上的存储格式。以下是它们之间的关系和区别：

1. **写入过程**：
    - 在LSM树中，新的写入操作首先被写入内存中的结构（通常是Memtable），当Memtable达到一定大小后，它会被写入磁盘，形成一个不可变的SSTable文件。
    - SSTable的数据写入过程是：数据首先写入内存表，当内存表达到阈值时，转化为SSTable文件并写入磁盘。

2. **数据结构**：
    - LSM树包含两部分：Memtable（内存中的KV查找树）和SSTable（磁盘上的有序文件）。
    - SSTable是LSM树在磁盘上的物理表现形式，存储有序的键值对。

3. **合并操作（Compaction）**：
    - LSM树定期执行合并操作，将多个SSTable文件合并为一个新的SSTable文件，以减少磁盘碎片和提高读取性能。
    - SSTable的合并操作是将多个小的SSTable文件合并为一个更大的SSTable文件，减少磁盘碎片和读取开销。

4. **读取过程**：
    - 在LSM树中，读取操作会先检查Memtable，然后检查磁盘上的SSTable文件，直到找到数据或确定数据不存在。
    - SSTable的数据查找过程与LSM树基本相同，都是从内存表和磁盘文件中逐个查找。

5. **磁盘存储和内存使用**：
    - LSM树通过将Memtable写入磁盘为SSTable文件来保证数据持久化，同时在内存中维护Memtable，占用较多内存空间。
    - SSTable通过将内存表转化为SSTable文件写入磁盘，保证数据持久化，同时需要在内存中维护内存表。

综上所述，SSTable是LSM树在磁盘上的存储和组织方式，而LSM树是管理和操作这些SSTable文件的逻辑结构。它们共同工作以提供高效的写入性能和合理的读取性能，尤其是在写入密集型的应用场景中。


SSTable（Sorted String Table）是一种用于存储结构化数据的格式，它在许多基于LSM树（Log-Structured Merge Tree）的数据库系统中使用，如LevelDB和BigTable。SSTable的核心原理是将数据存储为不可变的、排序的键值对集合，这使得写入操作非常高效，同时通过合并（Compaction）操作来优化读取性能。

### SSTable的原理

SSTable由几个关键部分组成：

1. **Data Block**：存放连续的数据块，每个数据块包含一系列的键值对（key-value pairs）。

2. **Block Index**：存放连续的块索引，描述一个data block，存储着对应data block的最大Key值，以及data block在文件中的偏移量和大小。

3. **Bloom Filter**：布隆过滤器，用于判断读取的数据是否在当前SSTable上。

4. **Table Schema**：当前SSTable的表格Schema信息。

5. **Fixed Trailer**：当前SSTable的Block Index的块索引大小。

6. **Trailer Offset**：当前SSTable的Block Index的块索引在文件存储下的偏移量。

### 举例说明

假设我们有一个简单的数据库表，包含两列：ID和Name，现在我们要插入三条记录：

1. ID=1, Name="Alice"
2. ID=2, Name="Bob"
3. ID=3, Name="Charlie"

当这些数据被写入SSTable时，它们会被存储为排序的键值对。由于ID是递增的，键值对也会按照ID排序：

- Key="1", Value="Alice"
- Key="2", Value="Bob"
- Key="3", Value="Charlie"

这些键值对会被组织成Data Block。每个Data Block都会有一个Block Index，记录该Block中的最大Key和在文件中的偏移量及大小。例如，如果第一个Data Block包含了前两个键值对，它的Block Index条目可能是：

- 最大Key="2", 偏移量=0, 大小=50（假设每个键值对占用25字节）

接着，这些Data Block和它们的索引会被写入SSTable文件中。SSTable文件的末尾会有一个Footer，记录了Block Index的偏移量和大小，使得可以快速定位到Block Index。

当需要读取某个Key时，系统会使用Bloom Filter来检查这个Key是否存在于SSTable中。如果Bloom Filter指示Key可能存在，系统会查找Block Index来确定Key所在的Data Block，然后将该Block加载到内存中，最后在Block中查找具体的Key。

通过这种方式，SSTable提供了高效的写入性能和优化的读取性能，尤其是在写入密集型的应用场景中。同时，通过定期的Compaction操作，旧的SSTable文件会被合并，删除重复的Key，并优化存储空间。

SSTable的合并过程，也就是Compaction过程，是LSM树中非常重要的一部分，它涉及到将多个SSTable文件合并成更少的、更大的SSTable文件，以减少读取时需要检查的SSTable数量，并回收磁盘空间。以下是SSTable合并过程的详细说明：

1. **Minor Compaction**：
    - 当内存中的Memtable达到一定大小时，它会被写入磁盘，形成Level 0的SSTable文件。
    - 如果Level 0的SSTable文件数量增加，会影响读性能，因此需要定期进行后台的merging compaction。
    - Minor Compaction过程中，会读取一些SSTable文件和memtable的内容，并将它们合并写入一个新的SSTable中。
    - 这个过程完成后，源SSTable和memtable就可以被删除了。

2. **Major Compaction**：
    - 如果一个merging compaction是合并所有SSTable到一个SSTable，则这个过程称为major compaction。
    - 一次major compaction会将标记为删除的信息、数据删除，而其他两次compaction则会保留这些信息、数据（标记的形式）。
    - Major compaction可以将需要删除的数据真正的删除从而节省空间，并保持系统一致性。

3. **合并策略**：
    - SSTable有两种合并策略：Leveling Merge Policy和Tiered Merge Policy。
    - Leveling Merge Policy中，每个level仅有1个组件，L0和L1合并，合并到L1中。
    - Tiered Merge Policy中，每个Level有N个组件，合并后生成Level+1的一个新组件。

4. **合并过程举例**：
    - 假设有一个键A，其值在系统中被更新了三次，分别在不同的Memtable中。
    - 当这些Memtable被写入磁盘时，它们会变成L0层的SSTable，可能如下所示：SSTable_L0_1：A -> value1，SSTable_L0_2：A -> value2，SSTable_L0_3：A -> value3。
    - 随后，Compaction过程会被触发，将L0层的SSTable合并成一个新的SSTable，并且移动到L1层：SSTable_L1_1：A -> value3。
    - 在L1层，键A是全局有序的，因为只保留了最新的版本value3。

通过这样的合并过程，LSM树能够优化写入性能，同时通过定期的数据合并来减少读取操作时需要检查的SSTable数量，并且可以回收磁盘空间。