[20111223]索引键值在B tree索引块中的顺序.txt

[20111223]索引键值在B tree索引块中的顺序.txt

参考链接：http://www.adellera.it/blog/2009/05/24/order-keys-inside-index-blocks/

自己为了加强理解重复一下对方的测试！

1.建立测试表以及索引

2.转储对应的索引块:

3.查看:

注意看row#0 括号的数字,表示该键值的索引块的位置,col0是索引键值,col1是rowid。

4.在"row directory"中记录键值的具体位置：

-- 摘抄链接，不自己写了，以免出现不必要的错误：http://www.adellera.it/blog/2009/05/24/order-keys-inside-index-blocks/

    that is, the addresses in the row directory are ordered by the (binary) value of the key they point to - remember that you must swap the high and low 2-byte quantities in each 32-bit word (the usual little-endian ordering; I haven't checked whether the results would be different on a machine that is not little-endian, as my one - an x86 - is).
如果交换字节顺序，可以确定按照以上地址顺序排列的。说明在索引插入时，键值从底部插入，而排序仅仅需要修改这个row directory就ok了。这样插入效率比较高。

    The reason for this ordering is to improve the efficiency of typical visits to the index block. Consider a range scan, when the kernel has to find all the index keys contained in the search interval [min_extreme, max_extreme] (possibly min_extreme=max_extreme for equality predicates). As it is well known, the kernel first walks the branch blocks to identify  the leaf block that contains min_extreme (or max_extreme, but that would be the same for our discussion); then, it has to identify all the keys that are >= min_extreme and = min_extreme, and then walk the next entries in the row directory until it gets to the last one that is
    The advantage is huge, since visiting all the keys is a O( N ) operation, while a binary search has only O ( log(2,N) ) complexity.

    To fully appreciate this on a concrete example, consider that each key of our example needs 16+2 bytes of storage, hence a perfectly packed 8K block might contain approximately 8000 / 18 = 444 keys. Thanks to the ordering, for the very frequent equality search (classic for Primary Key searches for example), the processing consists essentially of the binary search  only - hence the number of keys to be considered are down to about ceil( log(2, 444) ) = 9, thus consuming only 9/444 = 2%
(!!) of the resources.

    It is also worth remembering that this way, only a portion of the block is accessed, thus needing less accesses to central memory (it is unlikely in fact that the whole 8K can be found in the processor's caches), thus reducing the elapsed time considerably since stalling for central memory is a very common bottleneck in database systems - and thus improving scalability for the whole system thanks to the reduction of the traffic on the memory bus.

    Of course there's a price to be paid for modifications, since each modification has to keep the row directory ordered, thus shifting the slots of the row directory, which is a relatively expensive operation. Oracle pays an higher bill at modification time to save (hugely) at read time.

--modify 代价很大!

    As a final observation: note that the branch block visit can be considered a binary search as well, "pre-calculated" by the B+tree structure - the ordering inside a block is just the same divide-and-conquer algorithm applied in a different way.