随笔

假如要对1,000,000条数据项进行检索，用什么样的方法能够快速的完成呢？
首先想到的是为每一条数据关联一个关键值，然后每条数据项以的形式存放在一个容器中，查找时，给出key，然后再到这个容器里检索出key值对应的项，自然就找到了想要检索的数据了。
然后就是找到一个合适的容器来保存这些项。hash容器就是一个很好的选择，因为它提供了O(1)的插入，删除和查找性能。但是它需要在初始化hash容器是预先知道其能存多少个数据项，并且后面不能再更改hash容器的大小。而在数据项数量可能的范围很大时，选择一个合适的大小是很困难的。因为在数据项数超出了容器能容纳的上限时，可以通过链表等方式继续向容器添加数据，但是它可能会使查找的性能退化到O(N)；在数据项的数目远小于hash容器容量时，又会造成客观的空间浪费。
如果将容器换成一个线性的容器，那么要查找出key值所在的项，其最好的时间复杂度为O(log₂N)，但是其前提是需要对这个N个数据进行排序，并保证数据存储在一个连续的区域内。假如数据项的数目是固定不变的，那么这样的方法简单而高效。但是如果数据可能增添或删除，则为了保证容器中各项的顺序，就有可能进行大范围的数据移动操作，导致数据的插入和删除的时间复杂度为O(N)。
为了改善数据插入和删除的性能，则可用平衡二叉树替代前面的线性容器。这样在进行插入和删除操作时，维护平衡二叉树的时间复杂度降为了O(log₂N)，同时还保证了查找的时间复杂度也同为O(log₂N)。这就很好的满足了先前的需求。在进一步，假如数据是存放在外存上且量很大，不能把所有的项全部放入内存中，再通过平衡二叉树进行数据查找是否同样能保证高效呢？
这时将要查找某项数据时，需要进行以下两个步骤：1.将数据节点载入主存；2.在主存中查找key值。而从外存载入数据到主存的时间相比于在主存里查找key值来说往往是非常耗时的，所以其查找性能，取决于数据I/O的次数。比如在1,000,000条数据中通过平衡二叉树查找某项数据时，所做的比较次数为?log₂1,000,000?=20次，这也就意味着最坏情况下有20次的载入操作。对于一个7200 转每分钟的磁盘，旋转周期大约是8.33毫秒。像希捷ST3500320NS这样的磁盘,磁道至磁道的寻道时间为 0.8毫秒，平均读取寻道时间为8.5毫秒。为了简化，假设从磁盘读取花费10毫秒。乐观来说，如此，在一百万中定位一笔记录将会话花费20次磁盘读取乘上10毫秒每次读取时间，总共是0.2秒。而CPU进行20次比较的时间则可忽略不计了。
为了减少I/O，可以将多个节点存放在同一个块上，那么就可以一次I/O就可以读入多个键值了。而这样的数据结构稍作调整则引出了b-tree，Knuth对它的定义如下（原文放上）:
    1. Every node has at most m children.
    2. Every non-leaf node (except root) has at least ?m?2? children.
    3. The root has at least two children if it is not a leaf node.
    4. A non-leaf node with k children contains k?1 keys.
    5. All leaves appear in the same level, and internal vertices carry no information.
比如右图中的b-tree其m=4。
可以看出b-tree中的一个node包含了多个key值，如果能使一个node在一次I/O中全部载入主存，其效率提升是非常可观的。具体性能分析可以参见。
b-tree的目的就是要减少I/O次数，以减少I/O时间，从而提升整体性能，但它不能减少key的比较次数。所以它在很多的文件系统中得到了应用，具体可参见【Ubiquit Btree】这篇论文。