TsDB2

TsDB2 - 时序数据库

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

目录

• 特性
• 架构设计
• 存储格式
• 索引实现
• 性能指标
• 快速开始
• 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+树节点
  表列表指针    索引元数据      目录索引        键值对

页面大小

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+ 树)

数据结构：

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 找到
重启后插入	成功
重启后更新	成功
重启后删除	成功

---

快速开始

安装

go get TsDB2

基本使用

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)
}

运行示例

# 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 操作

// 打开数据库
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 操作

// 创建索引
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 复用策略：

// 插入时优先查找有空间的相邻 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+ 树分裂

叶节点分裂：

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

内节点分裂：

// 提升右节点第一个 key 到父节点
promoKey := btKey(btEntry(right, 0))

已知限制

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

---

许可证

MIT License

---

联系方式

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