# TsDB2 - 时序数据库

TsDB2 是一个用 Go 语言实现的高性能时序数据库，支持多种索引类型（主键 B+ 树、时序索引、字符串二级索引、复合二级索引），提供完整的增删改查功能。

## 目录

- [特性](#特性)
- [架构设计](#架构设计)
- [存储格式](#存储格式)
- [索引实现](#索引实现)
- [性能指标](#性能指标)
- [快速开始](#快速开始)
- [API 文档](#api-文档)
- [项目结构](#项目结构)
- [技术细节](#技术细节)

---

## 特性

- **多种索引类型**
  - 主键索引：B+ 树实现，O(log n) 查询
  - 时序索引：针对时间序列数据优化
  - 字符串二级索引：支持字符串字段索引
  - 复合二级索引：支持多字段组合索引

- **完整 CRUD 操作**
  - Insert：支持多索引同步写入
  - Search：支持主键查询、二级索引查询
  - Update：原地更新或先删后插策略
  - Delete：支持级联删除多索引

- **高性能**
  - 10 万行数据：插入 1,007 rows/s，查询 62,897 rows/s
  - 空间优化：10 万行仅 12.93 MB（对比 SQLite 2 MB）
  - 页复用策略：DataPage 自动填充，避免空间浪费

- **数据持久化**
  - 进程重启后数据完整保留
  - 支持多表、多索引管理

---

## 架构设计

### 整体架构

```
┌─────────────────────────────────────────────────────────┐
│                      API Layer                          │
│  DB.Open() / CreateTable() / CreateIndex() / ...        │
└─────────────────────────────────────────────────────────┘
                            │
┌─────────────────────────────────────────────────────────┐
│                    Table Layer                          │
│  InsertRow() / SearchByIndex() / UpdateRow() / DeleteRow()│
└─────────────────────────────────────────────────────────┘
                            │
        ┌───────────────────┼───────────────────┐
        │                   │                   │
┌───────▼───────┐  ┌────────▼────────┐  ┌──────▼──────┐
│ Primary Index │  │ Secondary Index │  │  Compose    │
│   (B+ Tree)   │  │  (Str/Time)     │  │   Index     │
└───────┬───────┘  └────────┬────────┘  └──────┬──────┘
        │                   │                   │
┌───────▼───────────────────▼───────────────────▼──────┐
│                    DataPage Layer                    │
│  [PageHdr(18B)][Count(4B)][DirOffset(2B)][Max/Min]   │
│  [Data...][Dir...]                                   │
└──────────────────────────────────────────────────────┘
                            │
┌──────────────────────────────────────────────────────┐
│                    File Layer                        │
│  [HeadPage][TablePage][DataPage][IndexPage][HeapPage] │
└──────────────────────────────────────────────────────┘
```

### 页面类型

| 类型 | 标识 | 说明 |
|------|------|------|
| HeadPage | 0 | 数据库头部，存储魔数、版本、表列表 |
| TablePage | 1 | 表元数据，存储字段定义、索引元数据 |
| DataPage | 2 | 数据页，存储行数据 |
| HeapPage | 3 | 堆页，存储溢出数据 |
| IndexMetaPage | 4 | 索引元数据页 |
| IndexPage | 5 | B+ 树节点页 |

---

## 存储格式

### 数据库文件布局

```
┌─────────────┬─────────────┬─────────────┬─────────────┐
│  HeadPage   │  TablePage  │  DataPage   │ IndexPage   │
│   (4KB)     │   (4KB)     │   (16KB)    │   (16KB)    │
└─────────────┴─────────────┴─────────────┴─────────────┘
     │              │              │              │
     │              │              │              │
     ▼              ▼              ▼              ▼
  魔数+版本     表定义+字段     行数据存储     B+树节点
  表列表指针    索引元数据      目录索引        键值对
```

### 页面大小

```go
PageSize = 4096 * 4 = 16384 bytes (16KB)
HeaderSize = 4096 bytes (4KB)
```

### DataPage 格式

```
┌─────────────────────────────────────────────────────────┐
│ PageHdr (18B) │ Count (4B) │ DirOffset (2B) │ Max (8B) │ Min (8B) │
├─────────────────────────────────────────────────────────┤
│                    Data Area (16344B)                    │
│  ┌─────────────────────────────────────────────────┐    │
│  │ [rowLen(4B)][rowData...]  ← 从上往下增长         │    │
│  │ [rowLen(4B)][rowData...]                        │    │
│  │ ...                                             │    │
│  ├─────────────────────────────────────────────────┤    │
│  │                    空闲空间                      │    │
│  ├─────────────────────────────────────────────────┤    │
│  │ ...                                             │    │
│  │ [DirEntry(2B)]  ← 从下往上增长                  │    │
│  │ [DirEntry(2B)]                                  │    │
│  └─────────────────────────────────────────────────┘    │
└─────────────────────────────────────────────────────────┘
```

**行数据格式**：
```
[rowLen(4B)][pkID(8B)][field1][field2]...[fieldN]
```

- `rowLen`: 行数据总长度（不含 rowLen 本身）
- `pkID`: 主键 ID（LittleEndian）
- `fieldN`: 各字段值

### IndexPage (B+ 树节点) 格式

```
┌─────────────────────────────────────────────────────────┐
│ PageHdr (18B) │ IndexType (1B) │ EntryLen (2B) │        │
│ Count (4B) │ IsLeaf (1B) │ Padding (3B)                 │
├─────────────────────────────────────────────────────────┤
│                    Entries Area                          │
│  ┌─────────────────────────────────────────────────┐    │
│  │ [Key(8B)][PageID(4B)]  ← 每个条目 12 字节        │    │
│  │ [Key(8B)][PageID(4B)]                           │    │
│  │ ...                                             │    │
│  └─────────────────────────────────────────────────┘    │
└─────────────────────────────────────────────────────────┘
```

**B+ 树路由约定**：
- 内部节点：第一个 `Entry.Key > searchKey` 的条目，跟其 PageID
- 叶节点：找到第一个 `Entry.Key >= searchKey` 的条目

---

## 索引实现

### 1. 主键索引 (B+ 树)

**数据结构**：
```go
type IndexHead struct {
    Hdr       page.PageHdr    // 18 bytes
    IndexType index.IndexType // 1 byte
    EntryLen  uint16          // 2 bytes (固定 12)
    Count     uint32          // 4 bytes
    IsLeaf    byte            // 1 byte
}
```

**操作复杂度**：
| 操作 | 复杂度 | 说明 |
|------|--------|------|
| Search | O(log n) | 从根到叶二分查找 |
| Insert | O(log n) | 查找 + 叶分裂 |
| Delete | O(log n) | 查找 + 移除条目 |

**叶分裂策略**：
- 所有条目 + 新条目排序后平分到两个叶节点
- 内节点分裂时，提升右节点第一个 key 到父节点

**DataPage 复用策略**：
- 插入时优先查找有空间的相邻 DataPage
- 只有当所有相邻页都满时才创建新 DataPage
- 10 万行数据：从 10 万页降至约 400 页

### 2. 时序索引

针对时间序列数据优化，支持范围查询。

### 3. 字符串二级索引

支持字符串字段索引，用于非主键字段查询。

### 4. 复合二级索引

支持多字段组合索引，最多 16 个字段。

---

## 性能指标

### 10 万行数据测试 (3 个索引同时写入)

| 操作 | 数量 | 耗时 | 吞吐量 | 平均耗时/行 |
|------|------|------|--------|-------------|
| **插入** | 100,000 | 99.3s | 1,007 rows/s | 0.99 ms |
| **查询** (主键) | 100,000 | 1.59s | 62,897 rows/s | 15.9 μs |
| **删除** | 50,000 | 1.50s | 33,332 rows/s | 30 μs |
| **更新** | 50,000 | 1.85s | 27,077 rows/s | 37 μs |

### 空间占用

| 数据库 | 10 万行大小 | 对比 |
|--------|------------|------|
| **TsDB2** | 12.93 MB | - |
| **SQLite** | 2.02 MB | 基准 |
| **TsDB2 (优化前)** | 1,569 MB | 121 倍大 |

**空间分析** (10 万行)：
- 数据页: ~393 页 (100000 / 255 行每页)
- B+ 树索引页: ~400 页 (10 万条目)
- 二级索引: ~35 页
- 总计: ~828 页 × 16KB = 12.93 MB

### 持久性测试

| 测试项 | 结果 |
|--------|------|
| 进程重启后打开数据库 | 成功 |
| 验证 10 万条数据存在 | 100,000/100,000 找到 |
| 重启后插入 | 成功 |
| 重启后更新 | 成功 |
| 重启后删除 | 成功 |

---

## 快速开始

### 安装

```bash
go get TsDB2
```

### 基本使用

```go
package main

import (
    "TsDB2/DB"
    "TsDB2/DB/index"
    "TsDB2/DB/types"
    "encoding/binary"
)

func main() {
    // 打开数据库
    db, _ := DB.Open("test.db")
    defer db.Close()

    // 创建表
    table, _ := db.CreateTable("Users", []types.FieldInfo{
        {types.FieldType_8byte, []byte("ID")},      // 主键
        {types.FieldType_32byte, []byte("Name")},   // 名称
        {types.FieldType_2byte, []byte("Age")},     // 年龄
    })

    // 创建主键索引
    table.CreateIndex("pk_id", index.IndexTypePrimary, []byte{0})

    // 插入数据
    table.InsertRow([]types.FieldValue{
        {FieldName: []byte("ID"), Value: uint64(1)},
        {FieldName: []byte("Name"), Value: []byte("Alice")},
        {FieldName: []byte("Age"), Value: int16(25)},
    })

    // 查询数据
    key := make([]byte, 8)
    binary.BigEndian.PutUint64(key, 1)
    row, _ := table.SearchByIndex("pk_id", key)

    // 更新数据
    table.UpdateRow("pk_id", key, []types.FieldValue{
        {FieldName: []byte("ID"), Value: uint64(1)},
        {FieldName: []byte("Name"), Value: []byte("Alice_Update")},
        {FieldName: []byte("Age"), Value: int16(26)},
    })

    // 删除数据
    table.DeleteRow("pk_id", key)
}
```

### 运行示例

```bash
# B+ 树示例
cd demo
go run btree_demo.go

# 综合索引示例
go run all_index_demo.go

# 10 万行压力测试
go run stress_100k.go

# 持久性测试
go run persist_check.go
go run persist_check.go phase2
```

---

## API 文档

### DB 操作

```go
// 打开数据库
func Open(path string) (*DB, error)

// 创建表
func (db *DB) CreateTable(name string, fields []types.FieldInfo) (*Table, error)

// 查找表
func (db *DB) FindTable(name string) (*Table, bool)

// 删除表
func (db *DB) DropTable(name string) error

// 关闭数据库
func (db *DB) Close() error
```

### Table 操作

```go
// 创建索引
func (table *Table) CreateIndex(idxName string, typ index.IndexType, fields []byte) (*IndexMeta, error)

// 插入行
func (table *Table) InsertRow(fields []types.FieldValue) (uint64, error)

// 通过索引查询
func (table *Table) SearchByIndex(idxName string, key []byte) ([]types.FieldValue, error)

// 更新行
func (table *Table) UpdateRow(idxName string, key []byte, fields []types.FieldValue) error

// 删除行
func (table *Table) DeleteRow(idxName string, key []byte) error
```

### 字段类型

| 类型 | 大小 | 说明 |
|------|------|------|
| FieldType_1byte | 1B | int8 |
| FieldType_2byte | 2B | int16 |
| FieldType_4byte | 4B | int32 |
| FieldType_8byte | 8B | int64 / uint64 |
| FieldType_16byte | 16B | 定长字符串 |
| FieldType_32byte | 32B | 定长字符串 |
| FieldType_64byte | 64B | 定长字符串 |
| FieldType_128byte | 128B | 定长字符串 |
| FieldType_256byte | 256B | 定长字符串 |
| FieldType_Dynamicbyte | 12B | 动态数据（堆页存储） |

### 索引类型

| 类型 | 说明 |
|------|------|
| IndexTypePrimary | 主键索引（B+ 树） |
| IndexTypeTime | 时序索引 |
| IndexTypeStr | 字符串二级索引 |
| IndexTypeCompose | 复合二级索引 |

---

## 项目结构

```
TsDB2/
├── DB/                          # 核心数据库包
│   ├── db.go                    # 数据库操作
│   ├── Table.go                 # 表操作（CRUD 入口）
│   ├── const.go                 # 常量定义
│   ├── errors.go                # 错误定义
│   │
│   ├── DataPage.go              # 数据页实现
│   ├── IndexPage.go             # B+ 树节点操作
│   ├── IndexMetaPage.go         # 索引元数据管理
│   ├── HeadPage.go              # 数据库头部
│   ├── TablePage.go             # 表元数据页
│   ├── HeapPage.go              # 堆页（溢出存储）
│   │
│   ├── btree_ops.go             # B+ 树主流程集成
│   │
│   ├── inserter.go              # 插入逻辑
│   ├── query.go                 # 查询逻辑
│   ├── deleter.go               # 删除逻辑
│   ├── updater.go               # 更新逻辑
│   │
│   ├── condition.go             # 条件接口
│   ├── AndCondition.go          # AND 条件
│   ├── OrCondition.go           # OR 条件
│   ├── EqCondition.go           # = 条件
│   ├── GtCondition.go           # > 条件
│   ├── GeCondition.go           # >= 条件
│   ├── LtCondition.go           # < 条件
│   ├── LeCondition.go           # <= 条件
│   ├── LikeCondition.go         # LIKE 条件
│   ├── InCondition.go           # IN 条件
│   ├── NotCondition.go          # NOT 条件
│   │
│   ├── page/                    # 页面基础类型
│   │   └── BasePage.go          # PageHdr 定义
│   │
│   ├── types/                   # 类型定义
│   │   └── types.go             # FieldType, FieldValue
│   │
│   ├── index/                   # 索引实现
│   │   ├── ientry.go            # 索引条目接口
│   │   ├── primaryEntry.go      # 主键条目
│   │   ├── timeEntry.go         # 时间条目
│   │   ├── strKeyEntry.go       # 字符串条目
│   │   ├── composeEntry.go      # 复合条目
│   │   │
│   │   ├── btree/               # B+ 树主键索引
│   │   │   └── btree.go
│   │   │
│   │   ├── timedatapage/        # 时序数据页
│   │   │   └── datapage.go
│   │   │
│   │   ├── strdatapage/         # 字符串数据页
│   │   │   └── strdatapage.go
│   │   │
│   │   └── composepage/         # 复合索引数据页
│   │       └── composepage.go
│   │
│   ├── pool/                    # 内存池
│   │   └── pool.go
│   │
│   └── util/                    # 工具函数
│       └── utils.go
│
├── demo/                        # 示例程序
│   ├── btree_demo.go            # B+ 树示例
│   ├── time_demo.go             # 时序索引示例
│   ├── str_demo.go              # 字符串索引示例
│   ├── compose_demo.go          # 复合索引示例
│   ├── all_index_demo.go        # 综合索引测试
│   ├── stress_100k.go           # 10 万行压力测试
│   └── persist_check.go         # 持久性测试
│
├── main.go                      # 主程序入口
├── go.mod                       # Go 模块定义
└── README.md                    # 项目文档
```

---

## 技术细节

### 字节序处理

- **B+ 树索引键**: BigEndian
- **DataPage 存储行**: LittleEndian (pkID)
- **转换时机**: 搜索/删除/更新时，从 DataPage 读取 pkID 后转为 BigEndian 进行比较

### 更新策略

1. **原地更新**: 新数据 ≤ 旧数据时，直接覆盖
2. **先删后插**: 新数据 > 旧数据时，删除旧行，插入新行

### 删除级联

删除一行时，需要同步删除所有索引中的对应条目：
1. 通过指定索引找到 pkID
2. 从指定索引中删除条目
3. 从主键索引中删除数据行
4. 从所有二级索引中删除对应条目

### 空间优化

**DataPage 复用策略**：
```go
// 插入时优先查找有空间的相邻 DataPage
dpID, hasSpace := table.findSpaceInLeaf(rootPID, rowSize, key)
if hasSpace {
    // 复用已有 DataPage
    dp, _ := btreeLoadDP(table.handle, dpID)
    dp.appendRow(storeRowData)
    dp.save()
} else {
    // 创建新 DataPage
    dp := btreeNewDP(table.handle)
    dp.appendRow(storeRowData)
    dp.save()
}
```

### B+ 树分裂

**叶节点分裂**：
```go
// 所有条目 + 新条目排序后平分
all := make([]byte, total*12)
mid := total / 2
// 左叶: all[0:mid*12]
// 右叶: all[mid*12:total*12]
```

**内节点分裂**：
```go
// 提升右节点第一个 key 到父节点
promoKey := btKey(btEntry(right, 0))
```

### 已知限制

1. **删除 underflow 处理**: 当前跳过节点借/合并逻辑，允许节点欠满
2. **B+ 树条目冗余**: 为每个 key 存储一个条目，可优化为范围路由
3. **动态字段**: 超过 256 字节的数据使用堆页存储，性能较低

---

## 许可证

MIT License

---

## 联系方式

如有问题或建议，请提交 Issue 或 Pull Request。