下次自动登录
现在的位置:
& 综合 & 正文
Oracle B-Tree Index 原理
. B-Tree Index
No index structure can satisfy all needs, but the self-balancing B-tree index comes closest to optimizing the performance of searches on large sets of data. Each B-tree node holds multiple keys and pointers. The maximum number of keys in a node supported by a specific B-tree is the order of that tree. Each node has a potential of order+1 pointers to the level below it.
For example, the order=2 B-tree illustrated in
has tree pointers: to child nodes whose value is less than the first key, to the child nodes whose value is greater than the first key and less than the second key, and to the child nodes whose value is greater than the second key. Thus, the B-tree algorithm minimizes the number of reads and writes necessary to locate a record by passing through fewer nodes than in a binary tree algorithm, which has only one key and at most two children for each decision node. Here we describe the Knuth variation in which the index consists of two parts: a sequence set that provides fast sequential access to the data, and an index set that provides direct access to the sequence set.
Although the nodes of a B-tree generally do not contain the same number of data values, and they usually contain a certain amount of unused space, the B-tree algorithm ensures that the tree remains balanced and that the leaf nodes are at the same level.
OracleBtree Index3rootbranchleaf. Root.
rootbranchleafblock.
Branch,.Branchleaf(DBA)branchkdxbrlmc.
Oracle rdba dba
Leaf，以及相关索引键值的部分rowid(rowiddata object number)leaf 2(DBA)leafleaf.
Btree Index
Root Leaf .
Btree Index /.
Index Scan
sequential read,block(INDEX FAST FULL SCAN ).
Btree Index Update
delete,insert.
Btree Index
NullNullNull.
. Tree Index
SYS@anqing2(rac2)& select * from v$version where rownum=1;
----------------------------------------------------------------
Oracle Database 10g Enterprise Edition Release 10.2.0.4.0 - Prod
SYS@anqing2(rac2)& create table te as select * from
Table created.
SYS@anqing2(rac2)& select count(*)
----------
SYS@anqing2(rac2)& insert into te select * from dba_
50258 rows created.
SYS@anqing2(rac2)&
Commit complete.
SYS@anqing2(rac2)& select count(*)
----------
SYS@anqing2(rac2)& create index idx_te_object_name on te(object_name);
Index created.
2.2 Blevel, DBA_INDEXES.Blevel
*-Tree level: depth of the index from its root block to its leaf blocks. A depth of 0 indicates that the root block and leaf block are the same.
-- root block
leaf block. root block
leaf block
SYS@anqing2(rac2)& select index_name,blevel from dba_indexes where index_name='IDX_TE_OBJECT_NAME';
INDEX_NAME
------------------------------ ----------
IDX_TE_OBJECT_NAME
2.3 查看索引的height，索引的高度等于Blevel+1，height可以通过INDEX_STATS获得
SYS@anqing2(rac2)& select name,height from index_stats where name='IDX_TE_OBJECT_NAME';
no rows selected
--- index_stats analyze ... validate structure
SYS@anqing2(rac2)&
analyze index IDX_TE_OBJECT_NAME
Index analyzed.
SYS@anqing2(rac2)& select name,height from index_stats where name='IDX_TE_OBJECT_NAME';
------------------------------ ----------
IDX_TE_OBJECT_NAME
2.4 dump index
Btree index
treedumptreedumpobject_id
SYS@anqing2(rac2)& select object_id from dba_objects where object_name='IDX_TE_OBJECT_NAME' and owner='SYS';
----------
SYS@anqing2(rac2)& oradebug setmypid
Statement processed.
SYS@anqing2(rac2)& alter session set events 'immediate trace name treedump level 54769';
Session altered.
SYS@anqing2(rac2)& oradebug tracefile_name
/u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc
treedump trace
[oracle@rac2 ~]$ cat /u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc
/u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc
Oracle Database 10g Enterprise Edition Release 10.2.0.4.0 - Production
With the Partitioning, Real Application Clusters, OLAP, Data Mining
and Real Application Testing options
ORACLE_HOME = /u01/app/oracle/product/10.2.0/db_1
System name:
Node name:
2.6.18-194.el5
#1 SMP Tue Mar 16 21:52:43 EDT 2010
Instance name: anqing2
Redo thread mounted by this instance: 2
Oracle process number: 29
Unix process pid: 3865, image: oracle@rac2 (TNS V1-V3)
13:15:00.375
*** ACTION NAME:()
13:15:00.371
*** MODULE NAME:(sqlplus@rac2 (TNS V1-V3))
13:15:00.371
*** SERVICE NAME:(SYS$USERS)
13:15:00.371
*** SESSION ID:(130.5-06-27 13:15:00.371
----- begin tree dump
branch: 0x5922 (0: nrow: 2, level: 2)
branch: 0x8166 (-1: nrow: 250, level: 1)
leaf: 0x5923 (-1: nrow: 182 rrow: 182)
leaf: 0x5924 (0: nrow: 182 rrow: 182)
leaf: 0x5925 (1: nrow: 186 rrow: 186)
leaf: 0x5926 (2: nrow: 189 rrow: 189)
leaf: 0x5927 (3: nrow: 186 rrow: 186)
leaf: 0x5928 (4: nrow: 190 rrow: 190)
leaf: 0x5929 (5: nrow: 186 rrow: 186)
leaf: 0x4117ca : nrow: 178 rrow: 178)
leaf: 0x4117cb : nrow: 187 rrow: 187)
leaf: 0x4117cc : nrow: 182 rrow: 182)
leaf: 0x: nrow: 222 rrow: 222)
leaf: 0x: nrow: 201 rrow: 201)
leaf: 0x: nrow: 240 rrow: 240)
leaf: 0x: nrow: 226 rrow: 226)
leaf: 0x: nrow: 211 rrow: 211)
branch: 0x47 (0: nrow: 245, level: 1)
leaf: 0x8165 (-1: nrow: 229 rrow: 229)
leaf: 0x8167 (0: nrow: 218 rrow: 218)
leaf: 0x8168 (1: nrow: 231 rrow: 231)
leaf: 0x8297 (2: nrow: 249 rrow: 249)
leaf: 0x: nrow: 191 rrow: 191)
leaf: 0x: nrow: 180 rrow: 180)
leaf: 0x46 (243: nrow: 56 rrow: 56)
----- end tree dump
branch block DBA(data block address)10DBA
DBA (root 0,branch leaf -1)
level blockleaf(leaf level)
branch: 0x5922 (0: nrow: 2, level: 2)
branch block
level 2 branch block
leaf block 2,Blevel2,branch root block.
nrow:2 root blocknrow:2 22dump 2 branch block
branch: 0x5922 (0: nrow: 2, level: 2)
root block ,
SYS@anqing2(rac2)& select dbms_utility.data_block_address_file('4265922') FILE_ID,
dbms_utility.data_block_address_block('4265922') BLOCK_ID
---------- ----------
root blocksegment header+1,
SYS@anqing2(rac2)& select header_file,header_block from dba_segments where segment_name='IDX_TE
&&&&推荐文章:
【上篇】【下篇】用户名：Larry.Yue
文章数：214
评论数：402
访问量：566685
注册日期：
阅读量：1297
阅读量：3317
阅读量：584552
阅读量：470005
[匿名]51cto游客：
[匿名]王毅：
51CTO推荐博文
& & & & 我常常会听到一些同事对自己的SQL很有信心，往往说一句：“你看，已经走索引了”。但是我们真的使用了适合我们的索引吗？&&&&&&& 我抓取到一句SQL,消耗了太多的IO。&&&&&& &&&&&& select SMIN_INFOID,NVL(MI.MONU_PROVINCE,'未知'),COUNT(*) I_RESULTNUMFROM TBL_WAPXXX WARE,TBL_SMSXXX SMIN,TBL_MOBILEXXX MI,TBL_USERXXX USIN WHERE WARE_DATE & :B2 AND WARE_DATE &= :B2 + :B1 /24 &&&&&&&&&&&&AND WARE.WARE_UID_FK=USIN.USIN_UID_FK AND SUBSTR(USIN.USIN_PHNUM,1,7)=MI.MONU_PHONENUM(+) &&&&&&&&&&&&AND WARE_WRUIID_FK=SMIN.SMIN_INFOID GROUP BY SMIN_INFOID ,MI.MONU_PROVINCE&&&& 因为TBL_WAPXXX数据量比较大,而造成该SQL执行缓慢并且IO消耗高。看看它的SQL执行计划和成本估算(如下图)650) this.width=650;" onclick='window.open("/viewpic.php?refimg=" + this.src)' onclick="window.open("/viewpic.php?refimg=" + this.src)" src="../attachment/549852.jpg" alt="" border="0" />&&&&&&& 注意画框INDEX(为TBL_WAPXXX的相关索引)，虽然走了索引，但是成本和cardnility都很高。检查这个索引发现其实BLEVEL只有2。而再仔细查看SQL并询问实现的功能，其实索引的字段为DATE类型,该SQL只是检查最近几个小时的信息变化.&&&&&&& 在WHERE条件中(WARE_DATE & :B2)因为是范围查询,索引使用了(rang scan)，加之该表数据量众多(千万级别)，直接影响了SQL执行性能。&&&&&&&& 但是通过检查发现，这个索引就是直接创建的B-TREE索引。而我注意到其实该SQL检查的就是最近一个或几个小时的数据，终于可以找到一些问题所在了。INDEX建立时默认情况下，索引的字段采用升序(asc)建立，而这种方法显然是不适合当前这个SQL的，我们可以通过建立基于降序的索引来适应实际的需求。&&&&&&&& SQL& create index IDX_WARE_DATE1 on TBL_WAPXXXX(WARE_DATE desc)&&&&2&&&&&&&&tablespace USERTBS;&&& &&&&&&& 再来检查执行的SQL计划和预算成本:650) this.width=650;" onclick='window.open("/viewpic.php?refimg=" + this.src)' onclick="window.open("/viewpic.php?refimg=" + this.src)" style="width: 855 height: 241" src="../attachment/796316.jpg" alt="" border="0" />&&&&&&& 执行成本大幅降低。INDEX的建立时索引字段排序的方式其实对特定SQL影响还是很大的。尤其是一些历史流水表，在某些情况下只是查询近期的数据时，就显得尤为重要了。&&&&&&& 注：文中的SQL因为某些问题，我做了适当的处理，在显示的执行计划图中也是处理过的，所以会出现表名不十分匹配的问题，请大家见谅。&&&&&&& PS:&&&&&&&& 最近总是很忙，忙的只有在睡觉前才有时间写点东西。但是实在太累，总是无法好好的写。真的要好好坚持坚持呀 -:)，否则年初的目标就很难完成了。本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：┆阅读(0)┆评论(0)
11:57:33 16:01:30 14:08:30二元高度(Binary Height)
本文所属图书&>&
在Oracle认证大师Richard Niemiec的帮助下，系统地识别和排除数据库的性能问题：《Oracle Database 11g R2性能调整与优化》一书详细介绍了最新的监控、故障排除和优化的方法，取自真实世界的案例研究和最佳实&&
索引的二元高度对把ROWID返回给用户进程时所要求的I/O数量起到关键作用。二元高度的每个级别都会增加一个额外的块读取操作，而且由于这些块不能按顺序读取，它们都要求一个独立的I/O操作。在图2-1中，一个二元高度为3的索引，需要读4个块才能返回一行数据给用户，其中3次用来读索引，1次用来读表。随着索引的二元高度的增加，检索数据所要求的I/O次数也会随之增加。
在对索引进行分析后，可以通过查询DBA_INDEXES视图的BLEVEL列来查看它的二元高度：
图2-1& 二元高度(BLEVEL)为3的索引(Level 3为叶节点所在位置)
EXECUTE DBMS_STATS.GATHER_INDEX_STATS ('SCOTT','EMP_ID1');
PL/SQL procedure successfully completed.
select blevel, index_name
from dba_indexes
where index_name = 'EMP_ID1';
BLEVEL & INDEX_NAME
---------- ------------------------------
0 & EMP_ID1
分析索引或表可以得到索引的二元高度。使用USER_INDEXES视图里的BLEVEL列可以查看索引的二元高度。
表中索引列的非NULL值数量的增加和索引列中值的范围狭窄是二元高度增加的主要原因；索引上如果有大量被删除的行，它的二元高度也会增加。重建索引可能使二元高度降低。虽然这些步骤减少了针对索引执行的I/O数量，但对性能的改进却可能很小。如果一个索引中被删除的行接近20%~25%，重建索引会降低二元高度以及在一次I/O中所读取的索引块中的空闲空间。
一般来说，中的数据块越大，索引的二元高度就越低。二元高度每增加一个级别，在DML操作期间就会增加额外的性能成本。
关于BLEVEL和索引高度的更多细节
B树级别(BLEVEL)是指一个索引从它的根块到其叶块的深度。0层表明根块和叶块在同一个级别。所有索引都是从一个叶块开始，这时它代表了一颗0级的B树。当行被逐渐添加到索引中时，会把数据放到叶块中，随着不断有数据插入，一旦初始叶块填满，两个新块就会被创建出来。以两种方式处理这个操作，就是众所周知的90-10或50-50索引分裂法。被插入的值决定了使用哪种分裂方式：
●&&&&&&&& 如果新值大于该索引中已有任何值，那么Oracle将使用90-10分裂法，把当前块中的值复制到一个新块，将新值放到另外一个块中。
●&&&&&&&& 如果新值不是该索引中最大的值，那么Oracle会使用50-50分裂法，将较小的一半索引值放到一个新块中，将较大的另一半索引值放到另外一个新块中。
之前已经装满数据的块被更新成为只包含指向新叶块的指针的分支块，当前情况下也就是根块，这时索引就有1级分支了。随着行不断地插入索引，一个叶块填满时，Oracle将创建一个新的叶块。如果被插入的值大于当前叶块中的任何值，那么Oracle将把新值放到一个新块中；如果该值不是最大值，那么Oracle按值将块等分成两份(50-50分裂法)，将较小的值放到当前块中，将较大的值放到新块中。这时，这些叶块的分支块将更新为包含新块和现有块的指针。这种情况持续下去，直到分支块填满。当分支块填满时，Oracle会执行相同的块分裂操作：添加一个新的分支块，把当前分支块中的一半数据复制到新块中，将剩下的一半保留在现有的分支块中。这种方式不会增加索引的高度(BLEVEL)，它只是在查询遍历索引时提供了一个新的分支。只有在根节点填满并产生分裂时才会导致索引高度的增加。
只有在根节点分裂的情况下，索引会创建两个新块。当前的根块的内容被分割到两个新的分支块中，形成一个更高的索引树的顶部。根块的地址不会改变，通过在根块发生分裂时增加两个块，索引树总是平衡的。
1. 更新操作对索引的影响
索引只有在表中组成索引的列被更新时才会受到影响。因此，在许多情况下，更新操作根本不会影响索引。当更新组成索引的表列时，索引上会执行一个删除和插入的操作。旧值被标记为已删除，与原索引条目对应的一个新值被插入。因此，索引上没有真正意义上的&更新&。如果发现上述情况，您通常应该想到正在执行一个更新操作。索引条目也会通过Oracle的延迟块清理功能得以清理。只有在索引条目被删除而且块被清理后，索引块中的空间才能被新条目重用。
2. 删除操作对索引的影响
索引上的删除操作，并没有真正从索引中删除条目以获得空间。实际上，当表中一条记录被删除时，相应的索引条目被标记为已删除，在清理过程清理之前，仍然保留在索引中。最常见的清理索引条目的方法是通过在那个索引块上的插入操作。索引条目也可以通过Oracle的延迟块清理功能得以清理(这是发生在随后的查询，可能是一条SELECT语句)。在索引项将被删除，索引块被清理后，索引块中的空间可供新条目重复使用。
3. 更新和删除操作对索引的影响
围绕着删除和更新操作对索引的影响，一向众说纷纭，莫衷一是。前面已解释了Oracle索引上的删除和更新操作的基本工作原理，我们来仔细看看真实效果。删除操作实际是将索引条目标记为已删除，也就是说，删除操作仍然把数据留在叶块中，需要由清理过程清理。在对有条目标记为已删除的叶块进行插入操作时，会迫使这些条目被清理，使对叶块插入操作&重用&这些空间。是否有插入操作不会发生的情况？是的，但索引块最终被延迟块清理功能清理。
更新操作，伴随着在同一事务中对索引的删除/插入操作，往往会明显增大索引的大小，这种情况只有当您在同一事务大量执行这些操作才会发生(Oracle不建议这么做)。删除操作自身不会引起索引高度或BLEVEL的增加，只不过反映了如何重用被删除行所占空间的更大的问题。这意味着，在单个事务中大量删除或更新操作，或者两者都有的情况，可能造成索引的大小、高度和BLEVEL增加(Oracle不建议您在同一事务中执行大量DML操作)。此解决方案是通过提交(commit)来有效地制造大量的删除+插入操作事务，从而拆分原事务。这有助于重用空间，不会导致索引人为地增长到大于它应有的大小。这也解释了为什么在同一事务中包含大型删除和插入操作，通常会导致索引的增长。
在使人受益的博客上，Tom Kyte这样写道：
好了，事实上索引和人一样，有着自己希望维持的体重。人总是有的胖，有的瘦，有的高，有的矮。虽然可以通过节食来减肥，可人们还是容易变回到原来的体重。于索引而言也是一样：它们总要变得体阔腰圆，所以每个月都得被重建一回(让它们节食减肥)。而头半个月过后，索引就会再次发胖，并由于索引块分裂而产生大量的重做日志......
这个故事的寓意是使用本地管理的表空间以避免碎片和极少重建索引(首次正确建立索引，只有在性能与基准值比较后发生下降时才重建)。
4. 数据块大小对索引的影响
正如前面所述，从分支块到根块都可能分裂，这种行为会导致索引的高度和分支的增加。索引块分裂的次数，或者更具体地说，分支索引块分裂的次数，可以通过使用较大的索引块尽量减少。这是一些专家认为应使用更大的块创建索引表空间的一个原因。如果每个索引块能容纳更多的数据，索引分裂出现的频率将低很多，因此可以减少索引的分支和树叶块数。在旧的和新的数据块大小之间究竟该如何取舍呢？这大大取决于被索引数据量的大小。在衡量为索引使用更大的块大小，会对表空间产生多大的影响时需要谨慎。将索引移到具有更大的块大小的表空间时需要重建，这时会删除所有被标记为删除的条目，压缩索引使用空间，包括回收被标记为已删除的条目的空间和条目已经删除但还没有回收或重用的空间。因此，当您考虑到实际将要发生什么的时候，使用更大的块所产生的影响可能并不如预期或令人心动。
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
文章下载读书【图文】oracle索引_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
oracle索引
大小：303.45KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢}