# RaftDB Storage Engine Documentation

RaftDB 内置了一个高性能、线程安全的嵌入式键值存储引擎。该引擎专为 Raft 状态机设计，经过深度优化，采用 Radix Tree（基数树）作为核心索引结构。

## 1. 核心特性

*   **极速读写 (Blazing Fast)**: 基于 Radix Tree 的内存索引，支持数十万 QPS 的读写。
*   **高级查询 (Advanced Query)**: 支持前缀搜索、范围扫描，以及 `LIMIT/OFFSET` 下推优化。
*   **空间复用 (Disk Reuse)**: 内置 Best-Fit 策略的 FreeList，自动回收磁盘空间。
*   **热点缓存 (Hot Cache)**: 内置 LRU-style 缓存，加速热点数据读取。
*   **全文本支持 (Full Text)**: 基础的倒排索引架构（可扩展）。

## 2. 架构设计 (Architecture)

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

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

### 2.3 查询引擎 (Query Engine)
*   **Early Termination**: 支持 `LIMIT` 下推。一旦扫描满足数量，立即停止 IO 和遍历。
*   **Lazy Loading**: 仅在必要时（如过滤 Value 或返回结果）才从磁盘读取 Value。

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

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

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

| 操作类型 | 数量 | 耗时 | QPS (Ops/sec) | 提升幅度 (vs Hash版) |
| :--- | :--- | :--- | :--- | :--- |
| **Insert** | 100,000 | ~0.23s | **~436,000** | **9x** |
| **Update** | 10,000 | ~0.04s | **~250,000** | **2.5x** |
| **Insert (Reuse)** | 5,000 | ~0.01s | **~471,000** | **25x** |
| **Delete** | 10,000 | ~0.03s | **~382,000** | 持平 |

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

| 查询类型 | QPS (Ops/sec) | 说明 |
| :--- | :--- | :--- |
| **Point Lookup** | **~238,000** | 精确查询 `key="..."`。受限于 Radix 深度，略低于 Hash 但依然极快。 |
| **Meta Query** | **~80,000** | 前缀查询 `key like "prefix*"`。利用 Radix Tree 极速定位子树。**提升 33 倍**。 |
| **Limit Query** | **~290,000** | 分页查询 `LIMIT 10`。利用 Early Termination 立即返回。 |
| **Full Query** | ~26 | 全表扫描 `value like "*..."`。受限于单线程 IO 扫描 (优化空间所在)。 |

## 4. 使用说明

### 4.1 初始化

```go
import "db"

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

### 4.2 查询与分页

```go
// 极速前缀分页查询
// 引擎会自动识别 "user.*" 前缀，在 Radix Tree 上定位，并只扫描前 20 条
results, _ := e.Query(`key like "user.*" LIMIT 20`)
```

## 5. 优化路线图 (Roadmap)

目前的版本在 Key 操作上已经达到了极致。下一步的优化方向：
1.  **并发 Radix Tree**: 引入 `ART` (Adaptive Radix Tree) 或实现并发安全的 Radix Tree (CoW 或 Fine-grained locks) 以支持更高的并发读。
2.  **全文索引集成**: 将 `FullTextIndex` 深度集成到 `Query` 流程中，解决 `value like` 查询慢的问题。