# RaftDB Storage Engine Documentation

RaftDB 内置了一个高性能、线程安全的嵌入式键值存储引擎。该引擎专为 Raft 状态机设计，经过深度优化，采用 **Radix Tree (基数树)** 作为核心索引结构，并结合了 **倒排索引 (Inverted Index)** 以支持极速全文/模糊检索。

## 1. 核心特性

*   **极速读写 (Blazing Fast)**: 
    *   **Point Lookup**: ~23万 QPS (Radix Tree 内存索引)。
    *   **Insert/Update**: ~40-56万 QPS (Append-only Log + FreeList)。
*   **高级查询 (Advanced Query)**: 
    *   **Prefix/Range**: 基于 Radix Tree 的结构化扫描，性能随数据量增长极慢 (O(K))。
    *   **Full Text Search**: 针对 `value like` 查询引入倒排索引，性能提升 **20倍**。
    *   **Limit Pushdown**: 查询执行器支持 `LIMIT/OFFSET` 下推，扫描满足即停止。
*   **空间复用 (Disk Reuse)**: 内置 Best-Fit 策略的 FreeList，自动回收磁盘空间，无需手动 Compaction。
*   **热点缓存 (Hot Cache)**: 内置 LRU-style 缓存，减少 Syscall。

## 2. 架构设计 (Architecture)

### 2.1 核心索引: Radix Tree (Memory)
摒弃了传统的 Hash Map + Sharding 方案，采用单体 **Radix Tree**。
*   **优势**: 
    *   **有序性**: 天然支持 Key 的字典序遍历，无需排序。
    *   **前缀压缩**: 节省大量内存，特别适合 Key 具有公共前缀的场景。
    *   **范围查询**: `WalkPrefix` 操作复杂度仅为 O(K)。

### 2.2 辅助索引: Inverted Index (Memory)
针对 `value like "*token*"` 等模糊查询场景，引擎维护了一个轻量级的倒排索引 (Token -> Keys)。
*   **查询优化**: 当检测到查询包含特定 Token 时，查询规划器会跳过全表扫描，直接通过倒排索引定位 Candidate Keys。

### 2.3 存储层 (Storage Layer)
*   **Append-only Log**: 数据追加写入，保证崩溃恢复能力。
*   **In-Place Update**: 尝试原地更新（若空间足够），减少碎片。
*   **FreeList**: 维护空闲槽位，优先复用。
*   **Page Cache**: 简单的内存缓存层，减少系统调用。

## 3. 性能测试报告 (Benchmark Report)

测试环境: macOS, 10 并发 Workers, 本地磁盘 IO。

### 3.1 综合吞吐量 (Throughput)

| 操作类型 | 数量 | 耗时 | QPS (Ops/sec) | 说明 |
| :--- | :--- | :--- | :--- | :--- |
| **Insert** | 100,000 | ~0.25s | **~399,000** | 写入性能极强 |
| **Insert (Reuse)** | 5,000 | ~0.01s | **~560,000** | 空间复用路径极快 |
| **Update** | 10,000 | ~0.04s | **~252,000** | 原地更新优化生效 |
| **Delete** | 10,000 | ~0.02s | **~420,000** | 标记删除 |

### 3.2 查询性能 (Query Performance)

| 查询类型 | QPS (Ops/sec) | 提升幅度 | 说明 |
| :--- | :--- | :--- | :--- |
| **Point Lookup** | **~228,000** | - | 基准性能，极快。 |
| **Meta Query** | **~78,000** | **2x (vs SkipList)** | 前缀查询 `key like "prefix*"`。Radix Tree 核心优势。 |
| **Limit Query** | **~287,000** | **1.6x (vs SkipList)** | `LIMIT` 下推优化，扫描极少数据即返回。 |
| **Full Scan (Val)**| **~581** | **21.5x (vs Scan)** | **倒排索引生效**。从全表 IO 扫描变为内存索引查找。 |

## 4. 使用说明

### 4.1 初始化

```go
import "db"

e, err := db.NewEngine("./my_data")
if err != nil { panic(err) }
defer e.Close()
```

### 4.2 查询示例

```go
// 1. 极速前缀分页
// 引擎在 Radix Tree 上定位 "user." 子树，扫描前 20 条即停止
results, _ := e.Query(`key like "user.*" LIMIT 20`)

// 2. 高性能全文检索
// 引擎利用倒排索引直接定位包含 "error" 的记录，无需扫描全表
results, _ := e.Query(`value like "*error*"`)
```