简介:

提升查找的索引

较大程度上的提升是通过索引来做到的。在上面的例子中，初始磁盘读取从2个因素限制了查找范围。这基本上可以通过创建一个辅助索引来改善，这个索引包含每块磁盘块上的首笔记录（有时称为稀疏索引）。这个辅助索引可能只有原始数据库的1%大小，但是它可以更快速地被检索。在辅助索引中查找入口可以告诉我们在主数据库中要读去哪一块;查找辅助索引之后，我们只需要读取主数据库中的特定的某一个磁盘分块————通过一次磁盘读取开销。索引可以提供10,000入口，所以，这样最多需要14个比较级。就像主数据库，辅助索引中最后6个左右的比较级可能在相同的磁盘分块上。索引可以在大约8次磁盘读取中完成查找，目标记录会在9次磁盘读取后获得。

创建辅助索引的窍门是可以重复地给辅助索引创建辅助索引。那样可以实现一个只拥有100 入口，能填满一整个磁盘块的辅助-辅助索引。

要找到想要的记录，我们只需要读取3次磁盘分块，而不是14次。读取和查找辅助-辅助索引中第一个（而且是唯一的）块，标记了相应的辅助索引中的分块。读取和查找辅助索引的分块，标记了主数据库中相应的分块。我们只需要30毫秒，而不是150毫秒就能获取记录。

辅助的索引，使得查找问题从约为log2N 磁盘读取开销的二分查找，变成logbN 磁盘读取开销的查找，其中b为分块因素（每分块的入口数目：b = 100 入口每分块;logb1,000,000 = 3 次读取）。

在实际中，如果主数据库被频繁查找，辅助-辅助索引和大部分的辅助索引可能会存储在磁盘缓存中，所以它们不会产生磁盘读取。

插入和删除带来的麻烦

如果数据库不会改变，那么编制索引就很简单，而且索引永远不需要改变。如果他们会改变，那么管理数据库及其索引就变得非常麻烦。

从数据库中删除记录不会引起太大问题。索引可以保持不变，记录只需要标记为已删除。数据库仍然保持有序状态。如果会有很多删除，之后查找和存储就不再那么高效了。

在一个有序文件中进行插入将是个灾难，因为需要给插入的记录制造空间。在文件中第一笔记录后插入记录需要把所有记录向后偏移一个位置。如此的操作在实际中实在太过昂贵。

一种做法是预留一些空间给插入操作。磁盘块有一些空闲空间允许后来的插入，而不是高密度地填充。这些记录可以被标记为像是已删除的记录。

现在，只要块中存在空间，插入和删除都可以很快速。如果一个插入操作在一个块上找不到合适的空间，就在临近的块中寻找，且要调整辅助索引。期望是临近存在足够的空间，以免重新调整大量的块。作为可选方案，可以使用一些非排序的块。

B树运用的理念

B树使用了以上所有的想法。特别是：

• 保持键值有序，以顺序遍历

• 使用层次化的索引来最小化磁盘读取

• 使用不完全填充的块来加速插入和删除

• 通过优雅的遍历算法来保持索引平衡

另外，B树通过保证内部节点至少半满来最小化空间浪费。一棵B树可以处理任意数目的插入和删除。

文件系统中的B树

除了在数据库中使用之外，B树也用在文件系统中，以允许快速随机访问特定文件中的任意块。基本问题是转动文件块地址到磁盘块（或者可能是圆柱头扇区）地址。在讲解应用之前，我们看一下常见的存储结构：

我们计算机的主存基本都是随机访问存储器(Random-Access Memory，RAM)，他分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM比DRAM快，但是也贵的多，一般作为CPU的高速缓存，DRAM通常作为内存。这类存储器他们的结构和存储原理比较复杂，基本是使用电信号来保存信息的，不存在机器操作，所以访问速度非常快，具体的访问原理可以查看CSAPP，另外，他们是易失的，即如果断电，保存DRAM和SRAM保存的信息就会丢失。

我们使用的更多的是使用磁盘，磁盘能够保存大量的数据，从GB一直到TB级，但是 他的读取速度比较慢，因为涉及到机器操作，读取速度为毫秒级，从DRAM读速度比从磁盘度快10万倍，从SRAM读速度比从磁盘读快100万倍。下面来看下磁盘的结构：

如上图，磁盘由盘片构成,每个盘片有两面，又称为盘面(Surface)，这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴(spindle)，他使得盘片以固定的旋转速率旋转，通常是5400转每分钟(Revolution Per Minute,RPM)或者是7200RPM。磁盘包含一个多多个这样的盘片并封装在一个密封的容器内。上图左，展示了一个典型的磁盘表面结构。每个表面是由一组成为磁道(track)的同心圆组成的，每个磁道被划分为了一组扇区(sector).每个扇区包含相等数量的数据位，通常是（512）子节。扇区之间由一些间隔(gap)隔开,不存储数据。

以上是磁盘的物理结构，现在来看下磁盘的读写操作：

如上图，磁盘用读/写头来读写存储在磁性表面的位，而读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂，驱动器可以将读写头定位到任何磁道上，这称之为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到位的值，也可以修改值。对磁盘的访问时间分为 寻道时间，旋转时间，以及传送时间。

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建一个节点的同时，直接申请一个页的空间( 512或者1024)，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。如，将B树的度M设置为1024，这样在前面的例子中，600亿个元素中只需要小于4次查找即可定位到某一存储位置。

同时在B+树中，内节点只存储导航用到的key，并不存储具体值，这样内节点个数较少，能够全部读取到主存中，外接点存储key及值，并且顺序排列，具有良好的空间局部性。所以B及B+树比较适合与文件系统的数据结构。下面是一颗B树，用来进行内容存储。

他广泛用于文件系统及数据库中，如：

• Windows：HPFS文件系统
• Mac：HFS，HFS+文件系统
• Linux：ResiserFS，XFS，Ext3FS，JFS文件系统

B树与访问并发

通过将每个级别的树块与“下一个”指针链接在一起，可以避免所有读锁（因此并发访问得到极大改进）。这导致树结构，其中插入和搜索操作都从根到叶子。只有在修改树块时才需要写锁。这最大化了多个用户的访问并发性，这是数据库和/或其他基于B树的ISAM存储方法的重要考虑因素。与此改进相关的成本是在正常操作期间无法从btree中删除空页。

B树的弊端

• 除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

（其他关联数组的实现，例如三元搜索树或者开散列哈希表，可以动态适应任意长度的键值）。

参考以下文章和维基百科(有一部分为谷歌直接翻译过来的, 可能难以理解, 表示歉意!):

http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html