宁静致远

在B树的wiki页面上,有一小段内容介绍为什么数据库使用B树，很通俗易懂，推荐。

Time to search a sorted file
Usually, sorting and searching algorithms have been characterized by the number of comparison operations that must be performed using order notation. A binary search of a sorted table with N records, for example, can be done in O(log2N) comparisons. If the table had 1,000,000 records, then a specific record could be located with about 20 comparisons: log21,000,000 = 19.931….

Large databases have historically been kept on disk drives. The time to read a record on a disk drive can dominate the time needed to compare keys once the record is available. The time to read a record from a disk drive involves a seek time and a rotational delay. The seek time may be 0 to 20 or more milliseconds, and the rotational delay averages about half the rotation period. For a 7200 RPM drive, the rotation period is 8.33 milliseconds. For a drive such as the Seagate ST3500320NS, the track-to-track seek time is 0.8 milliseconds and the average reading seek time is 8.5 milliseconds.[2] For simplicity, assume reading from disk takes about 10 milliseconds.

Naively, then, the time to locate one record out of a million would take 20 disk reads times 10 milliseconds per disk read, which is 0.2 second.

The time won’t be that bad because individual records are grouped together in a disk block. A disk block might be 16 kilobytes. If each record is 160 bytes, then 100 records could be stored in each block. The disk read time above was actually for an entire block. Once the disk head is in position, one or more disk blocks can be read with little delay. With 100 records per block, the last 6 or so comparisons don’t need to do any disk reads—the comparisons are all within the last disk block read.

To speed the search further, the first 13 to 14 comparisons (which each required a disk access) must be sped up.

有序文件的查找时间

排序和查找算法通常使用“比较次数”衡量。举例来说，对含N条记录的有序表进行二分查询，需要做O(log2N)次比较。如果表中有100万条记录，那么查找特定记录，需要进行20次比较: log21,000,000 = 19.931。

大型数据库通常将数据保存在磁盘中。比较key时间将主要消耗在磁盘读取。磁盘读取时间包含两部分：磁头寻道时间和盘片旋转延时。寻道时间大约是0~20ms，甚至更多；平均旋转延时是一半的盘片旋转周期。7200RPM的磁盘，旋转周期大约为8.3ms。以Seagate ST3500320NS为例，trace-to-track的寻道时间大约0.8ms，平均读寻道时间为8.5ms。简单起见，假设从磁盘读需要10ms。

再简单假设在100w条记录中查找需要20次磁盘读，那么一次查询需要0.2s。

实际时间不会这么糟糕，因为记录实际上是分组分布在“磁盘块”上。假定磁盘块是16k，每条记录是160字节，那么：在一个磁盘块上可以存储100条记录。而上述分析的磁盘读时间实际上会读入一整个块。一旦磁头的位置适合，再读入数据的延时会变少。当一个块中有100条记录时，那么最后6次的比较不需要进行磁盘读(数据已在最后一次读的块中)。

为了进一步加速查找，我们需要优化前13~14次查询，这些查询都需要一次磁盘访问。

An index speeds the search

A significant improvement can be made with an index. In the example above, initial disk reads narrowed the search range by a factor of two. That can be improved substantially by creating an auxiliary index that contains the first record in each disk block (sometimes called a sparse index). This auxiliary index would be 1% of the size of the original database, but it can be searched more quickly. Finding an entry in the auxiliary index would tell us which block to search in the main database; after searching the auxiliary index, we would have to search only that one block of the main database—at a cost of one more disk read. The index would hold 10,000 entries, so it would take at most 14 comparisons. Like the main database, the last 6 or so comparisons in the aux index would be on the same disk block. The index could be searched in about 8 disk reads, and the desired record could be accessed in 9 disk reads.

The trick of creating an auxiliary index can be repeated to make an auxiliary index to the auxiliary index. That would make an aux-aux index that would need only 100 entries and would fit in one disk block.

Instead of reading 14 disk blocks to find the desired record, we only need to read 3 blocks. Reading and searching the first (and only) block of the aux-aux index identifies the relevant block in aux-index. Reading and searching that aux-index block identifies the relevant block in the main database. Instead of 150 milliseconds, we need only 30 milliseconds to get the record.

The auxiliary indices have turned the search problem from a binary search requiring roughly log2N disk reads to one requiring only logbN disk reads where b is the blocking factor (the number of entries per block: b = 100 entries per block; logb1,000,000 = 3 reads).

In practice, if the main database is being frequently searched, the aux-aux index and much of the aux index may reside in a disk cache, so they would not incur a disk read.

加速索引

索引能带来显著地改善。在上面的例子中，第一次磁盘读将搜索范围缩小一半。可以创建索引优化，索引中包含每一个磁盘块的第一个记录(称之为“稀疏索引”)。这个索引只有原数据库1%的大小，但却可以进行很快的查找。在索引找到的记录会告诉我们数据在哪个块，在查找索引完成后，只需要在主数据库找到相应的块，代价是一次磁盘读。索引中有1万个记录，所以它只需要14次比较，与主数据库一样，最后6次比较只需要一次磁盘读，因为它们在同一个磁盘块上。在索引中的查找需要8次磁盘读，查找到需要记录总共需要9次磁盘读。

这种创建索引的技巧可以嵌套使用：为索引创建索引。在我们的例子中，索引的索引只有100个记录，可以放进一个磁盘块。

因此，我们实际上只需要3次磁盘读就可以找到记录，而不是14次。一次磁盘读取到索引的索引，就可以定位到相关的索引块；再通过索引块就可以找到数据块。这样我们查找一条记录的时间只需要30ms。

索引改变了查找问题：原本需要log2N次磁盘读，现在只需要logbN，b是块因子(每个磁盘块含有的记录数，上例中b=100, log100 1000000=3)。

在实际读频繁的数据库中，索引的索引以及大部分索引都会在磁盘cache中，还可以节省下来磁盘读。

Insertions and deletions cause trouble

If the database does not change, then compiling the index is simple to do, and the index need never be changed. If there are changes, then managing the database and its index becomes more complicated.

Deleting records from a database doesn’t cause much trouble. The index can stay the same, and the record can just be marked as deleted. The database stays in sorted order. If there are a lot of deletions, then the searching and storage become less efficient.

Insertions are a disaster in a sorted sequential file because room for the inserted record must be made. Inserting a record before the first record in the file requires shifting all of the records down one. Such an operation is just too expensive to be practical.

A trick is to leave some space lying around to be used for insertions. Instead of densely storing all the records in a block, the block can have some free space to allow for subsequent insertions. Those records would be marked as if they were "deleted" records.

Now, both insertions and deletions are fast as long as space is available on a block. If an insertion won’t fit on the block, then some free space on some nearby block must be found and the auxiliary indices adjusted. The hope is enough space is nearby that a lot of blocks do not need to be reorganized. Alternatively, some out-of-sequence disk blocks may be used.

插入和删除带来的问题

如果数据库不改变，那么创建索引很简单，也不会被改变。但如果存在更改操作，数据库及索引的维护就会变得复杂的多。

删除记录不会带来太大的问题。索引可以仍然存在，只需要将记录标记为己删除。数据库仍然保持有序。但如果有大量的删除，查找效率和存储空间浪费较多。

在有序文件中插入记录会导致灾难，因为需要空间存放插入的纪录。如果在第一条记录前插入一条，那么整个文件中的记录都需要向后移动。这样的操作在实际中代价过于昂贵。

一个技巧是预留一些空间，不写满磁盘块，而是留一些空白为后续的插入准备空间。这些记录可以标记为“已删除”。

现在如果块中空间足够，插入和删除都很快了。但如果插入的记录空间不够，就需要在附近的块中找到一些空间出来，并且索引需要做相应的调整。我们只能寄希望于附近的块有足够的空间，否则就需要大量的磁盘块。有的地方使用了替换方案，一部分块可以乱序。

The B-tree uses all those ideas
The B-tree uses all the above ideas. It keeps the records in sorted order so they may be sequentially traversed. It uses a hierarchical index to minimize the number of disk reads. The index is elegantly adjusted with a recursive algorithm. The B-tree uses partially full blocks to speed insertions and deletions. In addition, a B-tree minimizes waste by making sure the interior nodes are at least 1/2 full. A B-tree can handle an arbitrary number of insertions and deletions.

集大成者：B树

B树包含了上述所有的思想：

• 记录有序组织，方便顺序遍历
• 采用多层索引来最小化磁盘读
• 优雅的递归组织索引
• 数据块预留空间以加速插入和删除，另外，它会最小化空间浪费，内部节点至少1/2满
• 可以处理任意数量的插入和删除