版权声明: 允许非商业性转载，但转载时必须标明原作者 fcicq、原始链接 http://www.fcicq.net/wp/?p=892 及本声明。
2009 年以索引技术创业的 TokuTek 发布了 TokuDB for MySQL, 看性能参数是挺不错的.当时就对它产生了极大的兴趣. 但非常不幸偶没有理解它的索引原理 (Tokutek 也不说). 再加上它不是很成熟, 没有 ACID, 多核支持也不好, 所以暂时搁置了.
设有 n 个数据吧.基本意思是有 log2(n) 个索引块, 块的大小分别是 1, 2, 4… 直到 2^k, 其和大于 n (要不就存不下了 
). 每个块只有空和填满两种状态.插入时如果碰到块满的情况就把两个小块合并为更大的块.因为较小的块可以在内存中合并 (反正内存中怎么折腾都不会慢的), 对较大的块来说在旋转存储器上的归并速度也是很快的, 这就是 TokuDB 高速最直接的原因. 压缩是另一个加分的因素.
看来最大的问题就是, 两个块合成新块时, 如果两个块都很大就比较麻烦了.
删除的问题并不清楚. 不过考虑到它作为数据仓库的用途, 这一点可以暂时原谅. 删除也可以用对数据加 flag 的方法解决. 好像更新也不是简单的事情.看起来很像变种单机 BigTable, 只是不知道现在 Google 改造存储系统的情况如何.kumofs 的作者说 kumofs 是第二代分布式存储系统(彻底没有单点问题), 这个情况有感兴趣的自己去研究吧.
变长的数据是容易处理的. 搜索的复杂度降到 O(logB(N)), 存储的只要是块的位置(或编号)就可以了.事务(包括灾难恢复)和并行化可能是难度最大的部分.
说到对存储到硬盘上的数据进行整理, 就不得不提到 Reiser4 引入的 Dancing Tree.写入之前对 Block 做整理的操作, 这是一个比较有效的优化, 只是可惜了…
—
TokuDB 还有 covering index (试译: 覆盖索引) 的支持. 覆盖索引要求所有要查询的列都在索引之中.如果有 (a, b, c) 的覆盖索引, 则查询 select b, c where a = xx 这类是很快的.(覆盖索引和多维排序索引有什么区别? 如果后者不能完成这个任务, 那是 MySQL 的错, 这绝对不是首创)
但偶不明白二维索引的实现方式. 暂时继续抱怀疑态度.
复杂度分析对于研究算法来说是十分必要的.Point Query 的复杂度 O(logN/logB), 实际上就等于 O(logB(N)), 你是不是忘了换底公式了?关于插入的复杂度, 允许多个块写到一起(包括内存上的优化)是非常显然的优化. 但随机插入的场合如果不能减少 IO 的话可不行.Fractal Tree 索引的效率和内存的关系并不大, 但实现上看起来挺吃 CPU 的.仔细想来, Fractal Tree Index 大批量的插入均摊复杂度确实是 O(logN / B).
—
Tokutek 的收费政策是生产环境未压缩纯数据(不算索引) 50 GB 以下不收费,包括所有的副本(也就是说 Replication 的话就要算多次了), 当然也没有技术支持.
超过部分每 100 GB / 年收费 $1000 (换算一下是 $0.83 / GB * Month ).Tokutek 认为单台机器能承担 5 TB 的数据, 这个数字偶是要怀疑的. 而且偶不愿意承担单点的风险.显然可以谈个优惠价出来, 实际上偶愿意接受的价格不超过 $0.05 / GB * Month.这个收费比 GAE DataStore 和 Amazon SimpleDB 都贵太多了, 实在不合算. 有人还在想 Oracle 怎样怎样…
换一个角度说, 如果你用 NoSQL 存数据, 用它当索引(注意别涉及删除问题), 偶想肯定不会超过 50 GB 的 这个引擎存文本虽然没问题, 可是偶肯定不会这样推荐的.
—
TokuDB 的下载页面提供了 Fractal Tree Library 的下载, 只有 x86_64 的版本.(需要注册, 随便填填就过了, 需要验证 E-Mail, 没有审核)解压出来有一个大号的 .so 文件, include 目录下有 tokudb.h. 实现还算是比较完整. 提供了测试的程序, 但有说要是作为嵌入式数据库的话需要获得许可.
其他：
http://openquery.com/blog/tokuteks-fractal-tree-indexes