分形树索引(Fractal Tree)

定义

分形树索引(Fractal Tree Index)是一种写优化的树形索引结构,由 Tokutek 公司(创始团队来自 MIT、Rutgers 等校的算法研究者)商业化,理论基础是缓存无关(cache-oblivious)算法与 B^ε 树。其代表产品是 MySQL 存储引擎 TokuDB 与 MongoDB 引擎 TokuMX。

原理

传统 B 树每次写入都要下沉到叶子节点,产生随机 IO。分形树在每个内部节点设置消息缓冲区:插入、删除、更新先作为消息存入根节点附近的缓冲区,缓冲区满后整批下推到子节点,层层传递直至叶子。一次 IO 搬运大量消息,把随机小写变成批量顺序写,写放大大幅降低,同时保持与 B 树同级的查询复杂度。

特性与现状

TokuDB 以高压缩比、大表高速插入和在线加索引著称。Tokutek 于 2015 年被 Percona 收购,TokuDB 后因维护成本停止开发,Percona 转向 MyRocks,但分形树的"消息缓冲下推"思想深刻影响了后续写优化引擎的设计。