本文翻译自?tokumx fractal tree(r) indexes, what are they? tokumx的一大创新在于，它打破了一条长久存在的关于数据库的规则：要保证好的写入性能，索引的工作集应当能够放在内存里。标准答案是这样的：如果索引的工作集比内存要大，写入就需要执行i/o，i/
本文翻译自?tokumx fractal tree(r) indexes, what are they?
tokumx的一大创新在于，它打破了一条长久存在的关于数据库的规则：要保证好的写入性能，索引的工作集应当能够放在内存里。标准答案是这样的：如果索引的工作集比内存要大，写入就需要执行i/o，i/o就会成为限制因素，性能就会下降。所以，要么让索引小到能全部放进内存，要么提供一种索引写入模式，避免工作集过大，比如mongodb所采用的，内存中只为最近插入的数据保存索引。
但对tokumx来说，这是绝对不成立的。依靠tokumx所提供的创新性的分形树索引，索引的工作集可以比内存更大，同时写入性能不受影响。分形树索引为什么在重度写入（无论是mongodb还是mysql）的评测中能表现优异，原因就在这里。
其他数据库仍在苦苦挣扎时，tokumx是如何提供这种写入性能的？做法就是将众多数据库（mongodb, mysql, berkelydb等等）使用的主要存储结构——b树索引，替换成为写入优化的数据结构——分形树索引。
“为写入优化的数据结构”意味着什么？
为了解这一点，首先你需要理解，为什么b树索引在索引超出内存限制时的表现会变差？下面是b树的图。
b树是种简单（同时美观）的数据结构。在b树中，内部节点存储支点（pivot）及指针，叶子节点存储全部真正的数据。在b树上插入时，需要找到数据对应叶子节点，再将数据写入。如果所有节点都在内存里，这样做的速度是很快的。但是如果大部分数据不在内存里（在上图中，只有内部节点和极少数叶子节点在内存里），检索叶子节点就需要执行i/o操作。其实，基本上所有的插入都会执行i/o操作。i/o的瓶颈就从这里来。写入性能下降的根源就在这里。如果硬盘每秒可以执行数百次i/o操作，那么b树充其量也只能执行这么几百次写入操作。所以mongodb和mysql会在iibench测试中败下阵来，自然而然地，用户会被告知“应当把索引的工作集保存在内存里”。
那么，分形树索引的速度为什么会快很多？简单说，它大量减少了i/o操作。下面解释原因。
分形树索引和b树索引的主要差别，解释了在内部节点中的写入性能差别。
使用b树时，内部节点只保存支点和指向各子节点的指针。使用分形树索引时，内部节点保存支点、指针，以及各子节点的缓冲区。
请注意，在上图中，每个内部节点中都有其子节点对应的缓冲区（灰色）。
依靠缓冲，写操作可以累积起来批量执行，所以整个过程是这样的：
从根节点出发，找到应当向下开始遍历的那个子节点将待定（pending）的写操作加入缓冲区如果该子节点对应的缓冲去还有空间，返回。否则，将待定的写操作刷到下一层节点的缓冲区中，腾出空间用于未来的写入。在根节点执行刷缓冲区，可能导致一系列的缓冲区刷新。也就是说，在根节点刷缓冲区可能将大量数据刷向其子节点，结果子节点的缓冲区也满了，于是它们也需要刷缓冲区。这种情况会持续发生，最终刷到叶子节点为止。
这种算法为什么会提供如此好的性能呢？简单说是减少了i/o（真的，关键就在i/o）。i/o的代价日益高昂，如果要执行i/o操作，总得有对应的回报来合算。如果使用b树索引，每插入一小篇文档，或者一行数据，或者一个键值对，就需要执行一次i/o。如果使用分形树索引，可以假设根节点是常驻内存的，所以我们知道，如果在某次写入时引发了了i/o操作，其实是写入了一整个缓冲区的数据。这可能包含很多文档（或者很多行，很多键值对…）。因为每个i/o操作其实归拢了很多写入，所以分形树索引大大减少了i/o操作的数量，也就解除了b树索引中的i/o瓶颈。
因为i/o的减少，分形树索引不会要求索引必须小于内存。即使超过内存的限制，tokumx依然可以维持很高的写入性能。
关于这种算法，还有一点也值得一提，如果数据都存在内存里，在写入性能上，分形树索引相对b树索引并没有算法上的优势。如果内存足够大，从算法来分析，b树和分形树都很快。
原文地址：翻译文档：tokumx的分形索引是什么？, 感谢原作者分享。