网易杭州研究院---胡争（博客：openinx.github.io） TokuDB索引结构 网易杭州研究院---胡争（博客：openinx.github.io）

TokuDB简介 基于分形树实现的MySQL存储引擎 Tokutek公司2007年研发，2013年开源 2015年Percona公司收购Tokutek公司 TokuDB内部的K-V存储引擎为ft-index TokuMx: ft-index + MongoDB Server层代码 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. MySQL Server层 MySQL Storage层 InnoDB TokuDB MyISAM Linux 文件系统层

TokuDB特点 更高性能，更低成本！ 支持事务（ACID）的MySQL存储引擎 插入性能大大高于InnoDB（分形树vs B+树） 在线执行DDL操作（不阻塞写操作） 超高压缩率（TokuDB 4M vs InnoDB 16K） 更高性能，更低成本！

分形树索引结构（一） 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2.

分形树结构（二） msg_buffer 先进先出队列 BasementNode（OMT） 弱平衡二叉树 增删改查期望复杂度O(logN) 扇出fanout默认[4,16]区间。

分形树结构（三） 叶子节点 数据量维持在[1M,4M]区间 数据量小于1M则合并 数据量大于4M则分裂。 非叶子节点 扇出（fanout）维持在[4,16]区间 扇出小于4则合并 扇出大于16则分裂。

分形树Insert/Update/Delete 步骤： a. 磁盘读取root节点页; b. 若root节点需分裂，则root节点一分为二，提升一个 新的Root节点; c. 若root节点是叶子节点，则插入到basementNode；否 则，append message到msg_buffer; d. 返回 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. 每次插入，Put msg到根节点就返回!

分形树Insert/Update/Delete root节点分裂 a. Root节点分裂前 A B C D E 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. C b. Root节点分裂后 A B D E

分形树Insert/Update/Delete a. B+树顺序插入热点数据分布图 分形树对应的热点数据分布图？ 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. b. B+树随机插入热点数据分布图

1. 异步flush msg_buffer消息到下层节点 当非叶子节点(height>0)的数据量超过4M时，表明该节点需要 flush； 找出该节点中所有msg_buffer数据量最大child，将(node,child) 添加到flush线程中。 将(node, child )节点中msg_buffer中所有的msg，都apply到 child指向的儿子节点（页）。 判断child指向的儿子节点(页)是否需要split或者merge。 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. 1. 异步flush msg_buffer消息到下层节点 2. 维持树形结构和高度 3. 牺牲写性能、提升读性能

分形树Point-Query 查找流程： 加载Root节点，通过二分搜索确定Key落在Root节点的 键值区间Range, 找到对应的Range的Child指针。 加载Child指针对应的的节点。 若该节点为非叶子节点， 则继续沿着分形树一直往下查找，一直到叶子节点停止。 若当前节点为叶子节点，则停止查找。 apply root节点到leaf节点上所有的消息到basementNode。 返回basementNode上key对应的value。 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2.

分形树Range-Query 分形树范围查询 B+树范围查询 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. B+树范围查询

TokuDB事务（一） Memory Page.1 Page.2 Page.3 Redo log (log**.toku) Disk LRU-Cache Memory Page.1 Page.2 Page.3 Redo log (log**.toku) Disk FractralTreeIndexFile(*.tokudb) Page.8 Page.9 Page.2 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. Undo log (tokudb.rollback)

TokuDB事务（二） 事务举例： begin; insert into student set id = 2, name='openinx'; commit; 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2.

TokuDB事务（三） Begin操作： 初始化txn对象，分配xid。 添加txn到事务管理器。 Insert操作： 插入{id=2,name='openinx'}到分形树中 =>添加消息到root节点 写日志到rollback。=>写undo 写xbegin操作到redolog（xbegin操作由begin之后的下一个更新操作 写入到redo log）。 写insert操作到redo log。 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. Commit操作： 写xcommit到redo log。 写日志到rollback日志。=>写undo 从事务管理器中删除txn。 fsync redolog到磁盘。

总结（一） B+树 分形树 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2. LSM树

总结（二） 1. golang的优点：并发编程。 具体版本支持： Google MySQL 5.1+, MariaDB 10.0+,  MySQL 5.6+ 2.

参考资料 http://github.com/Percona/tokudb-engine http://openinx.github.io/2015/11/25/ft-index-implement/ http://pan.baidu.com/s/1bnFkCEV

Thank you