TokuDB索引结构

• 语言: 中文（简体）
• 格式: .pdf
• 来源: openinx.github.io

摘要

文档介绍了TokuDB，一种基于分形树的MySQL存储引擎，由Tokutek公司开发并被Percona收购。TokuDB的内部存储引擎为ft-index，结合MongoDB的代码形成TokuMx。TokuDB在插入性能上优于InnoDB，但在查询性能上略逊一筹。文档还比较了TokuDB与其他存储引擎如InnoDB和LevelDB在事务支持、随机读写、压缩比率等方面的特点，强调了其高插入性能、在线DDL支持和高压缩率。TokuDB的分形树结构支持事务ACID，采用逻辑日志记录，并在随机写和顺序写方面表现出色。

AI总结

# TokuDB索引结构总结

## 1. TokuDB简介
- **基于分形树**实现的MySQL存储引擎。
- 开发背景：由Tokutek公司于2007年研发，2013年开源，2015年被Percona公司收购。
- 核心组件：
- **ft-index**：内部的键值存储引擎。
- **TokuMx**：基于ft-index + MongoDB Server层代码实现。

## 2. TokuDB与主流存储引擎对比
|特性 | InnoDB(B+树) | TokuDB(分形树) | LevelDB(LSM树) |
|---------------------|--------------|----------------|----------------|
|事务ACID | 支持 | 支持 | 不支持 |
|随机写性能 | 慢 | 快 | 非常快 |
|随机读性能 | 慢 | - | - |
|顺序写性能 | 最快 | - | - |
|顺序读性能 | 最快 | - | - |
|在线DDL支持 | 5.5前不支持，5.6后支持部分在线DDL | 支持 | 不支持 |
|undo-log用途 | 实现MVCC和回滚 | 仅用于回滚，MVCC由分形树结构支持 | 不支持 |
|redo-log类型 | 物理日志 | 逻辑日志 | 逻辑日志 |
|压缩比率 | 页16K，压缩比低 | 页4M，压缩比高 | - |
|适用场景 | 读多写少的OLTP业务 | 写多读少的OLTP业务 | 写多读少的OLAP业务 |

## 3. TokuDB性能特点
- **插入性能**：显著高于InnoDB（分形树 vs B+树）。
- **查询性能**：略低于InnoDB。
- **在线DDL支持**：不阻塞写操作。
- **压缩率**：页大小4M，压缩率远高于InnoDB（16K）。
- **总结**：更高性能，更低成本。

## 4. 分形树索引结构
- **分形树**（Fractal Tree）：
- ** BasementNode (OMT)**：弱平衡二叉树，增删改查复杂度为 $O(\log N)$。
- **页大小**：默认4M，扇出范围为4到16。
- **特性**：支持高并发插入和随机写入，适合写多读少的场景。

## 5. TokuDB事务机制
- **事务支持**：ACID合规。
- **事务流程**：
1. **Begin**：初始化事务对象，分配XID，添加到事务管理器。
2. **Insert**：将数据插入分形树，写入undo日志，写入redo日志（xbegin操作）。
3. **Commit**：写入xcommit到redo日志，写入undo日志，删除事务对象，同步redo日志到磁盘。

## 6. 总结
TokuDB基于分形树结构，适合写多读少的OLTP业务场景，具有高插入性能、高压缩率和在线DDL支持等优势，但在查询性能上略逊于InnoDB。其设计目标是通过高性能和低成本实现更优的存储解决方案。