现在的位置: 首页 > 数据库 > 正文

B树索特点及效率解读[转]

2014年10月31日 数据库 ⁄ 共 5080字 暂无评论 ⁄ 阅读 1,168 次
文章目录

Oracle B树特点

  • Oracle B树索引中不存在非唯一的条目。在非唯一索引中,Oracle会把rowid作为一个额外的列追加到键上,使得键唯一。如:create index I on T( x , y ) ,从概念上讲就是Create unique index I on T(x , y , rowid)。Oracle会首先按索引键值排序,然后再按照rowid升序排序。
  • 大多数情况下,Oracle B树索引的高度都是2或者3,所以一般情况下,在索引中找到一个键只需要2或3次I/O。
  • Oracle B树索引所有叶子块都应该在同一层上,并且叶子节点实际上都是双向链表,这样在进行索引区间扫描(index range scan)的时候,只需通过叶子节点的向前或者向后就可以了,无需再对索引结构进行导航。
  • 在唯一索引中,数据只按索引键值排序。
  • 适当对Oracle B树索引存在重复值的列进行压缩, 可以增加缓存命中率,使I/O数减少,因为相关的条目可能都存在在一个块中。(Exp:create index I on T(userid , username) username=’steven’这个值可能就会对应于多个rowid放在同一个索引块中);但是带来的负面作用是使索引结构复杂化,维护索引更耗时,查询索引占用CPU更多的时间。(压缩适合用于多列索引中)
  • Oracle B树索引的反向键索引主要用于缓解索引右侧缓冲区忙等待。适合用于类似于sequence产生的PK主键上,因为这些列不太会需要使用区间扫描,也就是不会用到max(PK),min(PK),between and或者where PK < 200等查询。
  • 如果在查询中会有order by colum1 asc,column2 desc, 试着在创建索引时create index I on T(colum1 asc,column2 desc) , 因为Oracle INDEX默认是DESC排序,在索引中排序总比在磁盘中排序好得多。
  • 适合Oracle B树索引使用的2种情况:访问表中占很小比例的行、根本不访问表,所需查询的数据全部在索引中。
  • 索引是按索引键顺序存储,索引会按键的有序顺序进行访问,而索引指向的块则随机存储在堆中。
  • 在“瘦表”(列或字段较少的表)中使用Oracle B树索引查询<2-3%的列,“胖表”中<20-25%的列,颤抖吧,如果你还说使用索引需要数据量不超过5%或10%。
  • 索引不存储NULL值,更准确的说是单列索引不存储NULL值,复合索引不存储全为NULL的值。索引不能存储NULL值,所以对这列采用IS NULL条件时会发生全表扫描。因为索引上根本没有NULL值,不能利用到索引。
  • 为什么索引列不能存NULL值?因为将索引列值进行建树时,其中必然涉及到诸多的比较操作。而NULL值参与的运算取值为NULL,这样的话NULL值实际上是不能参与进索引的过程。也就是说,NULL值不会像其他取值一样出现在索引树的叶子节点上。
  • 索引不适合建立在键值较少的列(重复数据较多的列),假如索引列TYPE有5个键值,如果有1万条数据,那么 WHERE TYPE = 1将访问表中的2000个数据块。再加上访问索引块,一共要访问大于200个的数据块。如果全表扫描,假设10条数据一个数据块,那么只需访问1000个数据块,既然全表扫描访问的数据块少一些,肯定就不会利用索引了。
  • 前导模糊查询不能利用索引(like '%XX'或者like '%XX%'),假如有这样一列code的值为'AAA','AAB','BAA','BAB' ,如果where code like '%AB'条件,由于前面是模糊的,所以不能利用索引的顺序,必须一个个去找,看是否满足条件。这样会导致全索引扫描或者全表扫描。如果是这样的条件where code like 'A % ',就可以查找CODE中A开头的CODE的位置,当碰到B开头的数据时,就可以停止查找了,因为后面的数据一定不满足要求。这样就可以利用索引了。

B树效率

我们从一个问题开始研究关于B树效率的问题,为什么在通过索引访问表时如果数据量比较大的话,使用索引反而会降低性能?

索引按索引键的顺序存储,按键的有序顺序进行访问。然而,索引指向的块则随机地存储在堆中。因此,我们通过索引访问表时,会执行大量分散、随机的I/O。

这里“分散”(scattered)是指,索引会告诉我们读取块1,然后是块1000、块205、块321、块1、块1032、块1,等等,它不会要求我们按一种连续的方式读取块1、然后是块2,接着是块3(原因在与表中的每一行并没有按照索引键的顺序存储在堆中,否则不会出现这种情况)。我们将以一种非常随意的方式读取和重新读取块,这种块I/O可能非常慢。也就是说,索引读取数据时是一次访问一个块读出一条数据。此时,可能使用全局扫描更快一些,原因就在于全局扫描一次读取一个块上的数据,这种读法可能造成整体I/O要小于使用索引,所以会出现不使用索引反而比使用索引效率高。

我们可以通过一个简单的例子来理解:

假设我们通过索引读取一个瘦表,而且要读取表中20%的行。若这个表中有100,000行,其中的20%就是2,0000行。如果行大小约为80字节,在一个块大小为8KB的数据库中,每个块上则有大约100行。这说明,这个表有大约1000个块。了解了这些情况,计算起来就非常容易了。

我们要通过索引读取20,000行,大约是20,000个TABLE ACCESS BY ROWID操作,再加上处理索引块的块,为此至少要处理20,000个表块来执行这个查询。不过,整个表才有大约1000个块!因而最后会平均把表中的每一个块读取和处理20次(效果就是缓存的命中率很低,缓存的相邻块的数据没有用到)。 即使把行的大小提高一个数量级,达到每行800字节,这样每块有11.行,现在表中就有11,000个块。要通过索引访问20,000行,仍要求我们把每一个块平均读取2次。

在这种情况下,全表扫描就比使用索引高效得多,因为每个块只会命中一次。如果查询使用这个索引来访问数据,效率都不会高,除非对于800字节的行,平均只访问表中不到5%的数据,因为这样一来,就只会访问大约5,000个块,如果是80字节的行,则访问的数据应当只占更小的百分比,大约0.5%或更少(这就是为什么在一次查询中一个“胖表”的数据获取百分比比一个“瘦表”相对高的原因)。

因此,根本原因是因为缓存命中率降低,出现了大量随机分散的I/O操作。

物理组织对索引效率的影响

此外,数据在磁盘上如何物理组织,对上述过程也会有显著影响。表会很自然地按主键顺序聚簇(因为数据或多或少就是已这种属性增加的)。当然,它不一定严格按照键聚簇(要想做到这一点,必须使用一个IOT),但是,一般来讲,主键值彼此接近的行的物理位置也会“靠“在一起。如果发出以下查询:

select * from T where primary_key between :x and :y;

你想要的行通常就位于同样的块上,在这种情况下,即使要访问大量的行(占很大的百分比),索引扫描可能效率也不会低。原因在于:我们需要读取和重新读取的数据库块很可能会被缓存,因为数据共同放置在同一个位置(co-located)。另一方面,如果行并非共同存储在一个位置上,使用这个索引对性能来讲可能就是灾难性的。

聚簇因子

USER_INDEXES视图中的CLUSTERING_FACTOR列,根据索引的值指示表中行的有序程度。如果这个值与块数接近,则说明表相当有序,得到了很好的组织,在这种情况下,同一个叶子块中的索引条目可能指向同一个数据块上的行。如果这个值与行数接近,表的次序可能就是非常随机的。在这种情况下,同一个叶子块上的索引条目不太可能指向同一个数据块上的行。

可以把聚簇因子(clusteringfactor)看作是通过索引读取整个表时对表执行的逻辑I/O次数。也就是说,CLUSTERING_FACTOR指示了表相对于索引本身的有序程度,查看这些索引时,会看到以下结果:

select a.index_name, b.num_rows,b.blocks,a.clustering_factor

from user_indexes a, user_tables b

where index_name in ('COLOCATED_PK', 'DISORGANIZED_PK' )

and a.table_name = b.table_name;

INDEX_NAME NUM_ROWS BLOCKS CLUSTERING_FACTOR

---------------   ---------- ---------- -----------------

COLOCATED_PK 100000 1252 1190

DISORGANIZED_PK 100000 1219 99932

所以数据库说:“如果通过索引COLOCATED_PK从头到尾地读取COLOCATED表中的每一行,就要执行1190次I/O。不过,如果我们对DISORGANIZED表做同样的事情,则会对这个表执行99,932次I/O“。之所以存在这么大的区别,原因在于,当Oracle对索引结构执行区间扫描时,如果它发现索引中的下一行几乎总与前一行在同一个数据库块上,就不会再执行另一个I/O从缓冲区缓存中获得表块。它已经有表块的一个句柄,只需直接使用就可以了。不过,如果下一行不在同一个块上,就会释放当前的这个块,而执行另一个I/O从缓冲区缓存获取要处理的下一个块。因此,在我们对索引执行区间扫描时,COLOCATED_PK索引会发现下一行几乎总于前一行在同一个块上。DISORGANIZED_PK索引发现的情况则恰好相反。

以上讨论的关键点是,索引并不一定总是合适的访问方法。优化器也许选择不使用索引,而且如前面的例子所示,这种选择可能很正确。影响优化器是否使用索引的因素有很多,包括物理数据布局。因此,你可能会矫枉过正,力图重建所有的表来使所有索引有一个好的聚簇因子,但是在大多数情况下这可能只会浪费时间。只有当你在对表中的大量数据(所占百分比很大)执行索引区间扫描时,这才会产生影响。另外必须记住,对于一个表来说,一般只有一个索引能有合适的聚簇因子!表中的行可能只以一种方式排序。在前面所示的例子中,如果Y列上还有一个索引,这个索引在COLOCATED表中可能就不能很好地聚簇,而在DISORGANIZED表中则恰好相反。如果你认为数据物理聚簇很重要,可以考虑使用一个IOT、B*树聚簇,或者在连续地重建表时考虑散列聚簇。

B树效率总结

什么时候建立索引,在哪些列上建立索引,你的设计中必须注意这些问题。索引并不一定就意味着更快的访问,甚至在许多情况下,如果Oracle使用索引,反而会使性能下降。我们可以从两个因素出发考虑,其中一个因素是通过索引需要访问表中多少数据(占多大的百分比),另一个因素是数据如何布局。

如果能完全使用索引“回答问题”(而不用表),那么访问大量的行(占很大的百分比)就是有意义的,因为这样可以避免读表所带来的额外的分散I/O。如果使用索引来访问表,可能就要确保只处理整个表中的很少一部分(只占很小的百分比)。应该在应用的设计期间考虑索引的设计和实现,而不要事后才想起来(我就经常见到这种情况)。如果对如何访问数据做了精心的计划和考虑,大多数情况下就能清楚地知道需要什么索引。

位图索引

位置索引对列的每个键值建立一个位图。特点:

  • 相对于B*Tree索引,占用的空间非常小,创建和使用非常快。位图索引由于只存储键值的起止Rowid和位图,占用的空间非常少。
  • 不适合键值较多的列。
  • 不适合update、insert、delete频繁的列。
  • 可以存储null值。B*Tree索引由于不记录空值,当基于is null的查询时,会使用全表扫描,而对位图索引列进行is null查询时,则可以使用索引。
  • 当select count(XX) 时,可以直接访问索引中一个位图就快速得出统计数据。
  • 当根据键值做and,or或 in(x,y,..)查询时,直接用索引的位图进行或运算,快速得出结果行数据。

散列索引

散列索引是根据HASH算法来构建的索引,所以检索速度很快,但不能范围查询。它只适合等值查询(包括= <> 和in),不适合模糊或范围查询。

 

参考文章:

http://blog.csdn.net/huanghui22/article/details/1347559

http://blog.csdn.net/knowhow/article/details/2042277

» 声明:本站文章源于个人经验总结或书籍、互联网转载,内容仅用于个人学习,请勿转载,否则后果自负!

给我留言

留言无头像?