本文翻译自 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树和分形树都很快。

建议继续学习：

1. 由浅入深探究mysql索引结构原理、性能分析与优化    (阅读：14618)
2. 浅谈MySQL索引背后的数据结构及算法    (阅读：9638)
3. 由浅入深理解索引的实现(2)    (阅读：6102)
4. HBase二级索引与Join    (阅读：5623)
5. 如何建立合适的索引？    (阅读：5136)
6. InnODB和MyISAM索引统计集合    (阅读：4978)
7. Innodb 表和索引结构    (阅读：4594)
8. mysql查询中利用索引的机制    (阅读：4416)
9. MySQL索引背后的数据结构及算法原理    (阅读：4283)
10. 多维度分类排行榜应用：用位图索引    (阅读：3938)