The Internal Structure of Indexes
Oracle uses B-trees to store indexes to speed up data access. With no indexes, you
have to do a sequential scan on the data to find a value. For n rows, the average
number of rows searched is n/2. This does not scale very well as data volumes
increase.
Consider an ordered list of the values divided into block-wide ranges (leaf blocks).
The end points of the ranges along with pointers to the blocks can be stored in a
search tree and a value in log(n) time for n entries could be found. This is the basic
principle behind Oracle indexes.
Figure 5–7 illustrates the structure of a B-tree index.
感觉上面标红的部分,理解起来有点麻烦.
字段意思似乎是这样：
1, 每个leaf block的end point(块末尾的指针),连同该指针指向的数据块,能够存储到搜索树中.
搜索树是什么？
这个表述想要表达一个什么意思呢？
2, 如果要在n个 index entry中搜索一个key value(暂不考虑是unique index还是nonuniqe index),
消耗的时间量级是 log(n), 这比全表扫描平均 n/2 性能要好.
有没有大虾能用通俗易懂的话解释一下呀,谢谢先!
[ 本帖最后由 tengrid 于 2008-9-24 19:42 编辑 ]
|
