深入研究B树索引

1、深入研究B树索引（一）2010-03-2501:43摘要：本文对B树索引的结构、内部管理等方面做了一个全面的介绍。同时深入探讨了一些与B树索引有关的广为流传的说法，比如删除记录对索引的影响，定期重建索引能解决许多性能问题等。B树索引的相关概念索引与表一样，也属于段（segment）的一种。里面存放了用户的数据，跟表一样需要占用磁盘空间。只不过，在索引里的数据存放形式与表里的数据存放形式非常的不一样。在理解索引时，可以想象一本书，其中书的内容就相当于表里的数据，而书前面的目录就相当于该表的索引。同时，通常情况下，索引所占用的磁盘空间要比表要小的多，其主要作用是为了加快对数据的搜索速度，也可以用来

2、保证数据的唯一性。但是，索引作为一种可选的数据结构，你可以选择为某个表里的创建索引，也可以不创建。这是因为一旦创建了索引，就意味着oracle对表进行DML（包才INSERTUPDATEDELETE时，必须处理额外的工作量（也就是对索引结构的维护）以及存储方面的开销。所以创建索引时，需要考虑创建索引所带来的查询性能方面的提高，与引起的额外的开销相比，是否值得。从物理上说，索引通常可以分为：分区和非分区索引、常规B树索引、位图（bitmap）索引、翻转（reverse）索引等。其中，B树索引属于最常见的索引，由于我们的这篇文章主要就是对B树索引所做的探讨，因此下面只要说到索引，都是指B树索引。B

3、树索引是一个典型的树结构，其包含的组件主要是：< !-if!supportLists->1）<!-endif->叶子节点（Leafnode）:包含条目直接指向表里的数据行。< !-if!supportLists->2）<!-endif->分支节点（Branchnode）:包含的条目指向索引里其他的分支节点或者是叶子节点。< !-if!supportLists->3）<!-endif->根节点（Rootnode）:一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。可以用下图一来描述B树索引的结构。其中，B表示分

4、支节点，而L表示叶子节点。8口R4300R5必RjfiS10RI5POORI6ORI29R21911R3痣0R25口口600R.10的。RI11W5R171200R1S100R1。加口R12了卯町1伽R14对于分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的最小键值；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索引块。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。比如

5、从上图一可以看到，对于根节点块来说，包含三条记录，分别为（0B1）、（500B2）、（1000B3）,它们指向三个分支节点块。其中的0、500和1000分别表示这三个分支节点块所链接的键值的最小值。而B1、B2和B3则表示所指向的三个分支节点块的地址。对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的ROWID,该ROWID是记录行在表里的物理

6、地址。如果索引是创建在非分区表上或者索引是分区表上的本地索引的话，则该ROWID占用6个字节；如果索引是创建在分区表上的全局索引的话，则该ROWID占用10个字节。知道这些信息以后，我们可以举个例子来说明如何估算每个索引能够包含多少条目，以及对于表来说，所产生的索引大约多大。对于每个索引块来说，缺省的PCTFRE时10%,也就是说最多只能使用其中的90%。同时9i以后，这90%中也不可能用尽，只能使用其中的87%左右。也就是说，8KB的数据块中能够实际用来存放索引数据的空间大约为6488（8192X9册X8a）个字节。假设我们有一个非分区表，表名为warecountd,其数据行数为130万行。

7、该表中有一个列，列名为goodid,其类型为char（8）,那么也就是说该goodid的长度为固定值：8。同时在该列上创建了一个B树索弓I。在叶子节点中，每个索引条目都会在数据块中占一行空间。每一行用2到3个字节作为行头，行头用来存放标记以及锁定类型等信息。同时，在第一个表示索引的键值的字段中，每一个索引列都有1个字节表示数据长度，后面则是该列具体的值。那么对于本例来说，在叶子节点中的一行所包含的数据大致如下图二所示：根节点:分支节.0R129R2190200R4300R340SR.7480500R9600RID699RI1_700R12_790R13792R14310R15900RI6310

8、05R17.1200R181300R191430RO1600R21叶子节.-11cmi190200300403500600699700790机01005120014801600表的数从上图可以看到，在本例的叶子节点中，一个索引条目占18个字节。同时我们知道8KB的数据块中真正可以用来存放索引条目的空间为6488字节，那么在本例中，一个数据块中大约可以放360(6488/18)个索引条目。而对于我们表中的130万条记录来说，则需要大约3611(1300000/360)个叶子节点块。而对于分支节点里的一个条目(一行)来说，由于它只需保存所链接的其他索引块的地址即可，而不需要保存具体的数据行在哪里，

9、因此它所占用的空间要比叶子节点要少。分支节点的一行中所存放的所链接的最小键值所需空间与上面所描述的叶子节点相同；而存放的索引块的地址只需要4个字节，比叶子节点中所存放的ROWID少了2个字节，少的这2个字节也就是ROWID中用来描述在数据块中的行号所需的空间。因此，本例中在分支节点中的一行所包含的数据大致如下图三所示：OBL500B2100(3B3B1B2B31000L714mLsLIL2L3L5L6L7200R4300<KR7-430RS310R15900R,1650。600R.10侬9RI1500LA700L5310L60U犯L240CU1W5R171200RIS00RI。;G0RI

10、2了如町1血R14ORI29R21卯2190200300403500TO079CSI01005120012ooNN不_KKX.ZE从上图可以看到，在本例的分支节点中，一个索引条目占16个字节。根据上面叶子节点相同的方式，我们可以知道一个分支索引块可以存放大约405(6488/16)个索引条目。而对于我们所需要的3611个叶子节点来说，则总共需要大约9个分支索引块。这样，我们就知道了我们的这个索引有2层，第一层为1个根节点，第二层为9个分支节点，而叶子节点数为3611个，所指向的表的行数为1300000行。但是要注意，在oracle的索引中，层级号是倒过来的，也就是说假设某个索引有N层，则根节点

11、白层级号为N,而根节点下一层的分支节点的层级号为N-1,依此类推。对本例来说，9个分支节点所在的层级号为1,而根节点所在的层级号为2。深入研究B树索引(二)2009-10-0222:12B树索引的内部结构我们可以使用如下方式将B树索引转储成树状结构的形式而呈现出来:altersessionsetevents'immediatetracenametreedumplevelINDEX_OBJECT_ID'比如，对于上面的例子来说，我们把创建在goodid上的名为idx_warecountd_goodid的索弓I转储出来。SQL>selectobject_idfromuser_

12、objectswhereobject_name='IDX_WARECOUNTD_GOODID'OBJECT_ID7378SQL>altersessionsetevents'immediatetracenametreedumplevel7378'打开转储出来的文件以后，我们可以看到类似下面的内容：begintreedumpbranch:0x180eb0a25225994(0:nrow:9,level:2)branch:0x180eca125226401(-1:nrow:405,level:1)leaf:0x180eb0b25225995(-1:nrow:35

13、9rrow:359)leaf:0x180eb0c25225996(0:nrow:359rrow:359)leaf:0x180eb0d25225997(1:nrow:359rrow:359)leaf:0x180eb0e25225998(2:nrow:359rrow:359),branch:0x180ee3825226808(0:nrow:406,level:1)leaf:0x180eca025226400(-1:nrow:359rrow:359)leaf:0x180eca225226402(0:nrow:359rrow:359)leaf:0x180eca325226403(1:nrow:359r

14、row:359)leaf:0x180eca425226404(2:nrow:359rrow:359)其中，每一行的第一列表示节点类型：branch表示分支节点(包括根节点)，而leaf则表示叶子节点；第二列表示十六进制表示的节点的地址；第三列表示十进制表示的节点的地址；第四列表示相对于前一个节点的位置，根节点从0开始计算，其他分支节点和叶子节点从-1开始计算；第五列的nrow表示当前节点中所含有的索引条目的数量。比如我们可以看到根节点中含有的nrow为9,表示根节点中含有9个索引条目，分别指向9个分支节点；第六列中的level表示分支节点的层级，对于叶子节点来说level都是0o第六列中的rr

15、ow表示有效的索引条目(因为索引条目如果被删除，不会立即被清除出索引块中。所以nrow减rrow的数量就表示已经被删除的索引条目数量)的数量，比如对于第一个leaf来说，其rrow为359,也就是说该叶子节点中存放了359个可用索引条目，分别指向表warecountd的359条记录。上面这种方式以树状形式转储整个索引。同时，我们可以转储一个索引节点来看看其中存放了些什么。转储的方式为：altersystemdumpdatafilefile#blockblock#;我们从上面转储结果中的第二行知道，索引的根节点的地址为25225994,因此我们先将其转换为文件号以及数据块号。SQL>sel

16、ectdbms_utility.data_block_address_file(25225994),2dbms_utility.data_block_address_block(25225994)fromdual;DBMS_UTILITY.DATA_BLOCK_ADDRESDBMS_UTILITY.DATA_BLOCK_ADDRES660170于是，我们转储根节点的内容。SQL>altersystemdumpdatafile6block60170;打开转储出来的跟踪文件，我们可以看到如下的索引头部的内容:headeraddress85594180=0x51a1044kdxcolev2KD

17、XCOLEVFlags=-kdxcolok0kdxcoopc0x80:pcode=0:iotflags=-isconverted=Ykdxconco2kdxcosdc0kdxconro8kdxcofbo44=0x2ckdxcofeo7918=0x1eeekdxcoavs7874kdxbrlmc25226401=0x180eca1kdxbrsno0kdxbrbksz8060其中的kdxcolev表示索引层级号，这里由于我们转储的是根节点，所以其层级号为2。对叶子节点来说该值为0;kdxcolok表示该索引上是否正在发生修改块结构的事务；kdxcoopc表示内部操作代码；kdxconco表示索引条

18、目中列的数量；kdxcosdc表示索引结构发生变化的数量，当你修改表里的某个索引键值时，该值增加；kdxconro表示当前索引节点中索引条目的数量，但是注意，不包括kdxbrlmc指针；kdxcofbo表示当前索引节点中可用空间的起始点相对当前块的位移量；kdxcofeo表示当前索引节点中可用空间的最尾端的相对当前块的位移量；kdxcoavs表示当前索引块中的可用空间总量，也就是用kdxcofeo减去kdxcofbo得到的。kdxbrlmc表示分支节点的地址，该分支节点存放了索引键值小于row#0（在转储文档后半部分显示）所含有的最小值的所有节点信息；kdxbrsno表示最后一个被修改的索引条

19、目号，这里看到是0,表示该索引是新建的索引；kdxbrbksz表示可用数据块的空间大小。实际从这里已经可以看到，即便是PCTFRE段置为0,也不能用足8192字节。再往下可以看到如下的内容。这部分内容就是在根节点中所记录的索引条目，总共是8个条目。再加上row#08043dba:25226808=0x180ee38col0;len8;(8):3130303030333932col1;len3;(3):01401arow#77918dba:25229599=0x180f91fcol0;len8;(8):3130303131323033col1;len4;(4):01408fa5kdxbrlmc所

20、指向的第一个分支节点，我们知道该根节点中总共存放了9个分支节点的索引条目，而这正是我们在前面所指出的为了管理3611个叶子节点，我们需要9个分支节点。每个索引条目都指向一个分支节点。其中col1表示所链接的分支节点的地址，该值经过一定的转换以后实际就是row#所在彳T的dba的值。如果根节点下没有其他的分支节点，则col1为TERMcol0表示该分支节点所链接的最小键值。其转换方式非常复杂，比如对于row#0来说，col0为3130303030303033,则将其中每对值都使用函数to_number(NN,'XX)的方式从十六进制转换为十进制，于是我们得到转换后的值：49,48,48,

21、48,48,48,48,51,因为我们已经知道索引键值是char类型的，所以对每个值都运用chr函数就可以得到被索引键值为：1000000&实际上，对10000003运用dump函数得到的结果就是：49,48,48,48,48,48,48,51。所以我们也就知道,10000003就是dba为25226808的索引块所链接的最小键值。SQL>selectdump('10000003')fromdual;DUMP('10000003')Typ=96Len=8:49,48,48,48,48,48,48,50接下来，我们从根节点中随便找一个分支节点，假设就

22、是row#0所描述的25226808。对其运用前面所介绍过的dbms_utility里的存储过程获得其文件号和数据块号，并对该数据块进行转储，其内容加下所示。可以row#08043dba:25226402=0x180eca2col0;len8;(8):3130303030333933col1;len3;(3):01402erow#404853dba:25226806=0x180ee36col0;len8;(8):3130303031363430col1;len3;(3):014009endofbranchblockdump发现内容与根节点完全类似，只不过该索引块中所包含的索引条目(指向叶子节点

23、)的数量更多了，为405个。这也与我们前面所说的一个分支索引块可以存放大约405(6488/16)个索引条目完全一致。然后，我们从中随便挑一个叶子节点，对其进行转储。假设就选row#0行所指向的叶子节点，根据dba的值：25226402可以知道，文件号为6,数据块号为60578。将其转储以后，其内容如下所示，我只显示与分支节点不同的部分。kdxlespl0kdxlende0kdxlenxt25226403=0x180eca3kdxleprv25226400=0x180eca0kdxledsz0kdxlebksz8036其中的kdxlespl表示当叶子节点被拆分时未提交的事务数量；kdxlend

24、e表示被删除的索引条目的数量；kdxlenxt表示当前叶子节点的下一个叶子节点的地址；kdxlprv表示当前叶子节点的上一个叶子节点的地址；kdxledsz表示可用空间，目前是0转储文件中接下来的部分就是索引条目部分，每个条目包含一个ROWID指向一个表里的数据行。如下所示。其中flag表示标记，比如删除标记等；而lock表示锁定信息。col0表示索引键值，其算法与我们在前面介绍分支节点时所说的算法一致。col1表示ROWID我们同样可以看到，该叶子节点中包含了359个索引条目，与我们前面所估计的一个叶子节点中大约可以放360个索引条目也是基本一致的。row#08018flag:,lock:0

25、col0;len8;(8):3130303030333933col1;len6;(6):01402e930016row#18000flag:,lock:0col0;len8;(8):3130303030333933col1;len6;(6):01402ee7000eJJJJrow#3581574flag:,lock:0col0;len8;(8):3130303030333937col1;len6;(6):014018ba001fendofleafblockdump深入研究B树索引(三)2009-10-0222:13B树索引的访问我们已经知道了B树索引的体系结构，那么当oracle需要访问索引里

26、的某个索引条目时，oracle是如何找到该索引条目所在的数据块的呢？当oracle进程需要访问数据文件里的数据块时，oracle会有两种类型的I/O操作方式:<!-if!supportLists->1)<!-endif->随机访问，每次读取一个数据块(通过等待事件“dbfilesequentialread”体现出来)。<!-if!supportLists->2)<!-endif->顺序访问，每次读取多个数据块(通过等待事件“dbfilescatteredread”体现出来)。第一种方式则是访问索引里的数据块，而第二种方式的I/O操作属于全表扫描。

27、这里顺带有一个问题，为何随机访问会对应到dbfilesequentialread等待事件，而顺序访问则会对应到dbfilescatteredread等待事件呢？这似乎反过来了，随机访问才应该是分散(scattered)的，而顺序访问才应该是顺序(sequential)的。其实，等待事件主要根据实际获取物理I/O块的方式来命名的，而不是根据其在I/O子系统的逻辑方式来命名的。下面对于如何获取索引数据块的方式中会对此进行说明。我们看到前面对B树索引的体系结构的描述，可以知道其为一个树状的立体结构。其对应到数据文件里的排列当然还是一个平面的形式，也就是像下面这样。因此，当oracle需要访问某个索引

28、块的时候，势必会在这个结构上跳跃的移动。/根/分支/分支/叶子/,/叶子/分支/叶子/叶子/,/叶子/分支/叶子/叶子/,/叶子/分支/.当oracle需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这股，最终访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到dbfilesequential

29、read等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时，oracle知道要访问所有的数据块，因此唯一的问题就是尽可能高效的访问这些数据块。因此，这时oracle可以采用同步的方式，分几批,同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的，因此其对应至Udbfilescatteredread等待事件。深入研究B树索引(四)2009-10-0222:18B树索引的管理机制4.1B树索引的对于插入(INSERT的管理对于B树索引的插入情况的描述，可以分为两种情况：一

30、种是在一个已经充满了数据的表上创建索引时，索引是怎么管理的；另一种则是当一行接着一行向表里插入或更新或删除数据时，索引是怎么管理的。对于第一种情况来说，比较简单。当在一个充满了数据的表上创建索引(createindex命令)时，oracle会先扫描表里的数据并对其进行排序，然后生成叶子节点。生成所有的叶子节点以后，根据叶子节点的数量生成若干层级的分支节点，最后生成根节点。这个过程是很清晰的。但是对于第二种情况来说，会复杂很多。我们结合一个例子来说明。为了方便起见，我们在一个数据块为2KB的表空间上创建一个测试表，并为该表创建一个索引，该索引同样位于2KB的表空间上。SQL>createt

31、ableindex_test(idchar(150)tablespacetbs_2k;SQL>createindexidx_testonindex_test(id)tablespacetbs_2k;当一开始在一个空的表上创建索引的时候，该索引没有根节点，只有一个叶子节点。我们以树状形式转储上面的索引idx_testoSQL>selectobject_idfromuser_objectswhereobject_name='IDX_TEST'OBJECT_ID7390SQL>altersessionsetevents'immediatetracenamet

32、reedumplevel7390'从转储文件可以看到，该索引中只有一个叶子节点(leaf)。begintreedumpleaf:0x1c001a229360546(0:nrow:0rrow:0)endtreedump随着数据不断被插入表里，该叶子节点中的索引条目也不断增加，当该叶子节点充满了索引条目而不能再放下新的索引条目时，该索引就必须扩张，必须再获取一个可用的叶子节点。这时，索引就包含了两个叶子节点，但是两个叶子节点不可能单独存在的，这时它们两必须有一个上级的分支节点，其实这也就是根节点了。于是，现在，我们的索引应该具有3个索引块，一个根节点，两个叶子节点。我们来做个试验看看这个过

33、程。我们先试着插入插入10条记录。注意，对于2KB的索引块同时PCTFRE囱缺省的10%来说，只能使用其中大约1623字节(2048X90%X88%)。对于表index_test来说，叶子节点中的每个索引条目所占的空间大约为161个字节(3个字节行头+1个字节列长+150个字节列本身+1个字节列长+6个字节ROWID,那么当我们插入将10条记录以后，将消耗掉大约1610个字节。SQL>begin2 foriin1.10loop3 insertintoindex_testvalues(rpad(to_char(i*2),150,'a');4 endloop;5 end;6

34、/SQL>commit;SQL>selectfile_id,block_id,blocksfromdba_extentswheresegment_name='IDX_TEST'FILE_IDBLOCK_IDBLOCKS741732SQL>altersystemdumpdatafile7block418;-因为第一个块为块头，不含数据，所以转储第二个块。打开跟踪文件以后，如下所示，可以发现418块仍然是一个叶子节点，包含10个索引条目，该索引块还没有被拆分。注意其中的kdxcoavs为226,说明可用空间还剩226个字节，说明还可以插入一条记录。之所以与前面计算

35、出来的只能放10条记录有出入，是因为可用的1623字节只是一个估计值。kdxcoavs226row#01087flag:lock:0col0;len150;(150):313061616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161

36、616161616161616161616161616161616161616161616161616161616161616161616161616161616161col1;len6;(6):01c001820004row#1926flag:,lock:0接下来，我们再次插入一条记录，以便基本充满该叶子节点，使得剩下的可用空间不足以再插入一条新的条目。如下所示。SQL>insertintoindex_testvalues(rpad(to_char(11*2),150,'a');这个时候我们再次转储418块以后会发现与前面转储的内容基本一致，只是又增加了一个索引条目。而

37、这个时候，如果向表里再次插入一条新的记录的话，该叶子节点(418块)必须进行拆分。SQL>insertintoindex_testvalues(rpad(to_char(12*2),150,'a');SQL>altersystemdumpdatafile7block418;转储出418块以后，我们会发现，该索引块从叶子节点变成了根节点(kdxcolev为1,同时row#0部分的col1为TERMS示根节点下没有其他分支节点)。这也就说明，当第一个叶子节点充满以后，进行分裂时，先获得两个可用的索引块作为新的叶子节点，然后将当前该叶子节点里所有的索引条目拷贝到这两个新获

38、得的叶子节点，最后将原来的叶子节点改变为根节点kdxcolev1,kdxbrlmc29360547=0x1c001a3,row#01909dba:29360548=0x1c001a4col0;len1;(1):34col1;TERMendofbranchblockdump同时，从上面的kdxbrlmc和row#0中的dba可以知道，该根节点分别指向29360547和29360548两个叶子节点。我们分别对这两个叶子节点进行转储看看里面放了些什么。SQL>selectdbms_utility.data_block_address_file(29360547),2dbms_utility.d

39、ata_block_address_block(29360547)fromdual;DBMS_UTILITY.DATA_BLOCK_ADDRESDBMS_UTILITY.DATA_BLOCK_ADDRES7419SQL>selectdbms_utility.data_block_address_file(29360548),2dbms_utility.data_block_address_block(29360548)fromdual;DBMS_UTILITY.DATA_BLOCK_ADDRESDBMS_UTILITY.DATA_BLOCK_ADDRES7420SQL>alters

40、ystemdumpdatafile7block419;SQL>altersystemdumpdatafile7block420;在打开跟踪文件之前，我们先来看看表index_test里存放了哪些数据SQL>selectsubstr(id,1,2)fromindex_testorderbysubstr(id,1,2);SUBSTR(ID,1,2)10121416182022242a4a6a8a打开419块的跟踪文件可以发现，里面存放了10、12、14、16、18、20、22、24和2a；而420块的跟踪文件中记录了4a、6a和8a。也就是说，由于最后我们插入24的缘故，导致整个叶子节

41、点发生分裂，从而将10、12、14、16、18、20、22、和2a放至ij419块里，而4a、6a和8a则放入420块里。然后，再将新的索引条目(24)插入对应的索引块里，也就是419块。假如我们再最后不是插入12*2,而是插入9会怎么样？我们重新测试一下，返回到index_test里有11条记录的情况下，然后我们再插入9。SQL>insertintoindex_testvalues(rpad('9',150,'a');这个时候，418块还是和原来一样变成了根节点，同时仍然生成出了2个叶子节点块，分别是419和420。但是有趣的是，419块里的内容与在插入

42、9之前的叶子节点（当时的418块）的内容完全相同，而420块里则只有一个索引条目，也就是新插入的9。这也就是说，由于最后我们插入9的缘故，导致整个叶子节点发生分裂。但是分裂过程与插入12*2的情况是不一样的，这时该叶子节点的内容不进行拆分，而是直接完全拷贝到一个新的叶子节点（419）里，然后将新插入的9放入另外一个新的叶子节点（420）。我们应该注意到，插入的这个9表里所有记录里的最大字符串。如果这时，我们再次插入12*2,则会发现419号节点的分裂过程和前面描述的一样，会将原来放在419块里的4a、6a和8a放入一个新的叶子节点里（421块），然后将12*2放入419块，于是这个时候419块

43、所含有的索引条目为10、12、14、16、18、20、22、和2a。同时420块没有发生变化。根据上面的测试结果，我们可以总结一下叶子节点的拆分过程。这个过程需要分成两种情况，一种是插入的键值不是最大值；另一种是插入的键值是最大值。对于第一种情况来说，当一个非最大键值要进入索引，但是发现所应进入的索引块不足以容纳当前键值时：从索引可用列表上获得一个新的索引数据块。将当前充满了的索引中的索引条目分成两部分，一部分是具有较小键值的，另一部分是具有较大键值的。Oracle会将具有较大键值的部分移入新的索引数据块，而较小键值的部分保持不动。将当前键值插入合适的索引块中，可能是原来空间不足的索引块，也可

44、能是新的索引块。更新原来空间不足的索引块的kdxlenxt信息，使其指向新的索引块。更新位于原来空间不足的索引块右边的索引块里的kdxleprv,使其指向新的索引块。向原来空间不足的索引块的上一级的分支索引块中添加一个索引条目，该索引条目中保存新的索引块里的最小键值，以及新的索引块的地址。从上面有关叶子节点分裂的过程可以看出，其过程是非常复杂的。因此如果发生的是第二种情况，则为了简化该分裂过程，oracle省略了上面的第二步，而是直接进入第三步，将新的键值插入新的索引块中。在上例中，当叶子节点越来越多，导致原来的根节点不足以存放新的索引条目（这些索引条目指向叶子节点）时，则该根节点必须进行分裂

45、。当根节点进行分裂时：从索引可用列表上获得两个新的索引数据块。将根节点中的索引条目分成两部分，这两部分分别放入两个新的索引块，从而形成两个新的分支节点。更新原来的根节点的索引条目，使其分别指向这两个新的索引块。因此，这时的索引层次就变成了2层。同时可以看出，根节点索引块在物理上始终都是同一个索引块。而随着数据量的不断增加，导致分支节点又要进行分裂。分支节点的分裂过程与根节点类似（实际上根节点分裂其实是分支节点分裂的一个特例而已）：从索引可用列表上获得一个新的索引数据块。将当前满了的分支节点里的索引条目分成两部分，较小键值的部分不动，而较大键值的部分移入新的索引块。将新的索引条目插入合适的分支索

46、引块。在上层分支索引块中添加一个新的索引条目，使其指向新加的分支索引块。当数据量再次不断增加，导致原来的根节点不足以存放新的索引条目（这些索引条目指向分支节点）时，再次引起根节点的分裂，其分裂过程与前面所说的由于叶子节点的增加而导致的根节点分裂的过程是一样的。同时，根节点分裂以后，索引的层级再次递增。由此可以看出，根据B树索引的分裂机制，一个B树索引始终都是平衡的。注意，这里的平衡是指每个叶子节点与根节点的距离都是相同的。同时，从索引的分裂机制可以看出，当插入的键值始终都是增大的时候，索引总是向右扩展；而当插入的键值始终都是减小的时候，索引则总是向左扩展。深入研究B树索引（五）2010-03-

47、2501:485.重建B树索引5.1 如何重建B树索引重建索引有两种方法：一种是最简单的，删除原索引，然后重建；第二种是使用ALTERINDEX,REBUILD命令对索引进行重建。第二种方式是从oracle7.3.3版本开始引入的，从而使得用户在重建索引时不必删除原索引再重新CREATEINDEX0ALTERINDEX,REBUILDS寸CREATEINDEX以下好处：2 !-if!supportLists->1)<!-endif->它使用原索引的叶子节点作为新索引的数据来源。我们知道，原索引的叶子节点的数据块通常都要比表里的数据块要少很多，因此进行的I/O就会减少；同时，由

48、于原索引的叶子节点里的索引条目已经排序了，因此在重建索引的过程中，所做的排序工作也要少的多。3 !-if!supportLists->2)<!-endif->自从oracle8.1.6以来，ALTERINDEX,REBUILD命令可以添加ONLINE®语。这使得在重建索引的过程中，用户可以继续对原来的索引进行修改，也就是说可以继续对表进行DMLB作。而同时，ALTERINDEX,REBUILD与CREATEINDEX有很多相同之处：4 !-if!supportLists->1)<!-endif->它们都可以通过添加PARALLEL提示进行并行处理。

49、5 !-if!supportLists->2)<!-endif->它们都可以通过添加NOLOGGING短语，使得重建索引的过程中产生最少的重做条目(redoentry)。<!-if!supportLists->3)<!-endif->自从oracle8.1.5以来，它们都可以田间COMPUTESTATISTICS语，从而在重建索引的过程中，就生成CBO所需要的统计信息，这样就避免了索引创建完毕以后再次运行analyze或dbms_stats来收集统计信息。当我们重建索引以后，在物理上所能获得的好处就是能够减少索引所占的空间大小(特别是能够减少叶子节点的

50、数量)。而索引大小减小以后，又能带来以下若干好处：<!-if!supportLists->1)<!-endif->CBO对于索引的使用可能会产生一个较小的成本值，从而在执行计划中选择使用索引。<!-if!supportLists->2)<!-endif->使用索引扫描的查询扫描的物理索引块会减少，从而提高效率。<!-if!supportLists->3)<!-endif->由于需要缓存的索引块减少了,从而让出了内存以供其他组件使用。尽管重建索引具有一定的好处，但是盲目的认为重建索引能够解决很多问题也是不正确的。比如我见过一

51、个生产系统，每隔一个月就要重建所有的索引(而且我相信，很多生产系统可能都会这么做)，其中包括一些100GB的大表。为了完成重建所有的索引，往往需要把这些工作分散到多个晚上进行。事实上，这是一个7X24的系统，仅重建索如果索引的层级超过X（X通常如果经常删除索引键值，则需如果索弓I的clustering_factor引一项任务就消耗了非常多的系统资源。但是每隔一段时间就重建索引有意义吗？这里就有一些关于重建索引的很流行的说法，主要包括：<!-if!supportLists->1）<!-endif->是3）级以后需要通过重建索引来降低其级别。<!-if!support

52、Lists->2）<!-endif->要定时重建索引来收回这些被删除的空间。<!-if!supportLists->3）<!-endif->很高，则需要重建索引来降低该值。<!-if!supportLists->4<!-endif->定期重建索引能够提高性能。对于第一点来说，我们在前面已经知道，B树索引是一棵在高度上平衡的树，所以重建索引基本不可能降低其级别，除非是极特殊的情况导致该索引有非常大量的碎片，导致B树索引“虚高”，那么这实际又来到第二点上（因为碎片通常都是由于删除引起的）。实际上，对于第一和第二点，我们应该通过运行A

53、LTERINDEX,REBUILD命令以后检查indest_stats.pct_used字段来判断是否有必要重建索引。5.2重建B树索引对于clustering_factor的影响而对于clustering_factor来说，它是用来比较索引的顺序程度与表的杂乱排序程度的一个度量。Oracle在计算某个clustering_factor时，会对每个索引键值查找对应到表的数据，在查找的过程中，会跟位从一个表的数据块跳转到另外一个数据块的次数（当然，它不可能真的这么做，源代码里只是简单的扫描索引，从而获得ROWID然后从这些ROWI威得表的数据块的地址）。每一次跳转时，有个计数器就会增加，最终该计

54、数器的值就是clustering_factor。下图四描述了这个原理。200R4300R5曳如700Ri27P0RI3偿RI4S10R1；mRLE侬R?钢R8JD0R9600P.1069CJR.111005R17_12001200RIPORI29R21WR3尊3940350070D79：3i0goQIQ0512001300图四在上图四中，我们有一个表，该表有4个数据块，以及20条记录。在列N1上有一个索引，上图中的每个小黑点就表示一个索引条目。列N1的值如图所示。而N1的索引的叶子节点包含的值为：A、B、C、DE、F。如果oracle开始扫描索引的底部，叶子节点包含的第一个N1值为A,那么根据

55、该值可以知道对应的ROWI现于第一个数据块的第三行里，所以我们的计数器增加1。同时，A值还对应第二个数据块的第四行，由于跳转到了不同的数据块上，所以计数器再加1。同样的，在处理B时，可以知道对应第一个数据块的第二行，由于我们从第二个数据块跳转到了第一个数据块，所以计数器再加1。同时，B值还对应了第一个数据块的第五行，由于我们这里没有发生跳转，所以计数器不用加1。在上面的图里，在表的每一行的下面都放了一个数字，它用来显示计数器跳转到该行时对应的值。当我们处理完索引的最后一个值时，我们在数据块上一共跳转了十次，所以该索引的clustering_factor为10。注意第二个数据块，clusteri

56、ng_factor为8出现了4次。因为在索引里N1为E所对应的4个索引条目都指向了同一个数据块。从而使得clustering_factor不再增长。同样的现象出现在第三个数据块中，它包含三条记录，它们的值都是C,对应的clustering_factor都是6。从clustering_factor的计算方法上可以看出，我们可以知道它的最小值就等于表所含有的反据块的数量；而最大值就是表所含有的记录的总行数。很明显，clustering_factor越小越好，越小说明通过索引查找表里的数据行时需要访问的表的数据块越少我们来看一个例子，来说明重建索引对于减小clustering_factor没有用处。

57、首先我们创建一个测试表：SQL>createtableclustfact_test(idnumber,namevarchar2(10);SQL>createindexidx_clustfact_testonclustfact_test(id);然后，我们插入十万条记录。SQL>begin2 foriin1.100000loop3 insertintoclustfact_testvalues(mod(i,200),to_char(i);4 endloop;5 commit;6 end;7 /因为使用了mod的关系，最终数据在表里排列的形式为：0,1,2,3,4,5,197,198,199,0,1,2,3,197,198,199,0,1,2,3,197,198,199,0,1,2,3,接下来，我们分析表。SQL>execdbms_stats.gather_t