组件
主要是：
叶子节点（Leaf node）：包含条目直接指向表里的数据行。
分支节点（Branch node）：包含的条目指向索引里其他的分支节点或者是叶子节点。
根节点（Branch node）：一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。
对于分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（可以指定reverse，倒序）。每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的最小键值（按B+tree最小键值复制原则）；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索引块。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。
对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的ROWID，该ROWID是记录行在表里的物理地址。在叶子节点中，每个索引条目都会在数据块中占一行空间。每一行用2到3个字节作为行头，行头用来存放标记以及锁定类型等信息。同时，在第一个表示索引的键值的字段中，每一个索引列都有1个字节表示数据长度，后面则是该列具体的值。
www.2cto.com
下面分别把分支节点的索引结构和叶子节点的索引信息dump出来
创建测试数据
查看索引的Blevel、height（blevel：节点的深度。root位于第0层，以此类推。height=blevel+1）
[sql]
sys@ORCL> select index_name,blevel from dba_indexes where index_name=‘BTREE_TT‘;
INDEX_NAME BLEVEL
------------------------------ ----------
BTREE_TT 2
sys@ORCL> analyze index btree_tt validate structure;
Index analyzed. www.2cto.com
sys@ORCL> select name,height from index_stats where name=‘BTREE_TT‘;
NAME HEIGHT
------------------------------ ----------
BTREE_TT 3
获得btree_tt的对象号，进行索引结构的dump
[sql]
sys@ORCL> select object_id from dba_objects where owner=‘SYS‘ and object_name=‘BTREE_TT‘;
OBJECT_ID
----------
52614
sys@ORCL> oradebug setmypid
Statement processed.
sys@ORCL> alter session set events ‘immediate trace name treedump level 52614‘;
www.2cto.com
Session altered.
sys@ORCL> oradebug tracefile_name
/u01/app/oracle/admin/orcl/udump/orcl_ora_5234.trc
查看treedump trc文件
[sql]
----- begin tree dump
branch: 0x40efaa 4255658 (0: nrow: 2, level: 2)
branch: 0x40f603 4257283 (-1: nrow: 247, level: 1)
leaf: 0x40efab 4255659 (-1: nrow: 182 rrow: 182)
leaf: 0x40efac 4255660 (0: nrow: 182 rrow: 182)
leaf: 0x40efad 4255661 (1: nrow: 186 rrow: 186)
leaf: 0x40efae 4255662 (2: nrow: 189 rrow: 189)
leaf: 0x40efaf 4255663 (3: nrow: 186 rrow: 186)
leaf: 0x40efb0 4255664 (4: nrow: 190 rrow: 190)
leaf: 0x40efb1 4255665 (5: nrow: 185 rrow: 185)
leaf: 0x40efb2 4255666 (6: nrow: 179 rrow: 179)
leaf: 0x40efb3 4255667 (7: nrow: 187 rrow: 187)
leaf: 0x40efb4 4255668 (8: nrow: 181 rrow: 181)
............................................
............................................
branch: 0x40f6fb 4257531 (0: nrow: 248, level: 1)
leaf: 0x40f602 4257282 (-1: nrow: 228 rrow: 228)
leaf: 0x40f604 4257284 (0: nrow: 226 rrow: 226)
leaf: 0x40f605 4257285 (1: nrow: 224 rrow: 224)
leaf: 0x40f606 4257286 (2: nrow: 223 rrow: 223)
leaf: 0x40f607 4257287 (3: nrow: 217 rrow: 217)
leaf: 0x40f608 4257288 (4: nrow: 253 rrow: 253)
leaf: 0x40f609 4257289 (5: nrow: 232 rrow: 232)
............................................
............................................
leaf: 0x40f6f8 4257528 (244: nrow: 191 rrow: 191)
leaf: 0x40f6f9 4257529 (245: nrow: 181 rrow: 181)
leaf: 0x40f6fa 4257530 (246: nrow: 99 rrow: 99)
----- end tree dump www.2cto.com
解释trc文件
每一行第一列表示：节点类型，branch是分支节点（包括了根节点），而leaf则是叶子节点
第二列表示：节点地址，16进制
第三列表示：节点地址，10进制
第四列表示：相对于前一个节点的位置：根节点从0算起，其他分支节点和叶子节点从1开始算
第五列表示：（nrow）当前节点所含索引条目的数量（包括delete的条目）
第六列表示：（level）分支节点的层级，在oracle的索引中，层级号是倒过来的，也就是说假设某个索引有N层，则根节点的层级号为N，而根节点下一层的分支节点的层级号为N-1
第七列表示：（rrow）有效的索引条目的数量，因为索引条目如果被删除，不会立即被清除出索引块中。所以nrow减rrow的数量就表示已经被删除的索引条目数量
上面这种方式以树状形式转储整个索引。同时，我们可以转储一个索引节点来看看其中存放了些什么。
下面转储根节点的索引块内容。
从trc文件可知：根节点branch: 0x40efaa 4255658 (0: nrow: 2, level: 2)
[sql]
sys@ORCL> select dbms_utility.data_block_address_file(4255658 ) fno，
2 dbms_utility.data_block_address_block(4255658 ) bno
3 from dual;
FNO BNO
---------- ----------
1 61354
sys@ORCL> alter system dump datafile 1 block 61354;
www.2cto.com
System altered.
sys@ORCL> oradebug tracefile_name
/u01/app/oracle/admin/orcl/udump/orcl_ora_5234.trc
查看root节点的trc内容
[sql]
header address 230057028=0xdb66444
kdxcolev 2
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 1
kdxcofbo 30=0x1e
kdxcofeo 8026=0x1f5a
kdxcoavs 7996
kdxbrlmc 4257283=0x40f603
kdxbrsno 0
kdxbrbksz 8056
kdxbr2urrc 0
row#0[8026] dba: 4257531=0x40f6fb
col 0; len 18; (18): 41 4c 4c 5f 43 4f 4c 5f 50 52 49 56 53 5f 4d 41 44 45
col 1; len 6; (6): 00 40 ee c5 00 2c www.2cto.com
----- end of branch block dump -----
kdxcolev 表示：索引层级号，我们这个例子中，根节点的level是2，叶子该是0
kdxcolok 表示：该索引上是否有DML活动事务
kdxconco 表示：索引条目中列的数量
kdxcosdc 表示：索引结构发生变化的数量，当你修改某个索引键值时，该值加1
kdxconro 表示：当前索引节点中索引条目的数量
kdxcofbo 表示：当前索引节点从第几个字节开始记录
kdxcofeo 表示：当前索引节点可用空间的最尾端在哪个字节
kdxcoavs 表示：当前索引节点可用空间总量。也就是kdxcofeo - kdxcofbo 的值
kdxbrlmc 表示：分支节点的位置
kdxbrsno 表示：最后一个被修改的索引条目号，这里为0，表明是新建索引
kdxbrbksz 表示：可用数据块大小，从这里我们可以知道，即便pctfree为0，对于8k数据块，我们也不能完全用完
[sql]
row#0[8026] dba: 4257531=0x40f6fb
col 0; len 18; (18): 41 4c 4c 5f 43 4f 4c 5f 50 52 49 56 53 5f 4d 41 44 45
col 1; len 6; (6): 00 40 ee c5 00 2c
这部分内容就是根节点里面记录的索引条目，总共1行（在B+树的定义里，如果按最小关键码复写原则，则树中每个非叶子节点中有m棵子树必有m-1个关键码）。每个索引条目都指向一个分支节点，其中，col 1表示所链接的分支节点的地址，如果根节点下没有其他的分支节点，则col 1为TERM；col 0表示该分支节点所链接的最小键值。注意一点，这里的col 0; len 18; (18):--列的行号，从0开始，紧接着的就是列的长度以及列的值，那么这个值称之为separator
key,这个separator key 可以区分真实的索引值，所以从这里我们也知道 branch block不会存储完整的索引值，只要能区分就行。也就是说，Oracle在 Branch block中只记录 索引键值的前缀，而不是所有值，是因为这样可以节约空间，从而能够存储更多的索引条目。同时，我们也能理解了为什么 查询使用 like ‘%xxx‘ 这种方法不会走Btree 索引，因为Branch block 存储的是前缀。
www.2cto.com
下面转储叶子节点块的内容
随便选一叶：leaf: 0x40f6fa 4257530 (246: nrow: 99 rrow: 99)
[sql]
sys@ORCL> select dbms_utility.data_block_address_file(4257530) fno,
2 dbms_utility.data_block_address_block(4257530) bno
3 from dual;
FNO BNO
---------- ----------
1 63226
sys@ORCL> oradebug setmypid
Statement processed.
sys@ORCL> alter system dump datafile 1 block 63226；
sys@ORCL> oradebug tracefile_name
/u01/app/oracle/admin/orcl/udump/orcl_ora_6177.trc
叶子节点的部分内容摘入如下：
[sql]
Block header dump: 0x0040f6fa
Object id on Block? Y
seg/obj: 0xcd86 csc: 0x00.a3506 itc: 2 flg: - typ: 2 - INDEX
fsl: 0 fnx: 0x0 ver: 0x01
Itl Xid Uba Flag Lck Scn/Fsc
0x01 0x0000.000.00000000 0x00000000.0000.00 ---- 0 fsc 0x0000.00000000
0x02 0xffff.000.00000000 0x00000000.0000.00 C--- 0 scn 0x0000.000a3506
www.2cto.com
Leaf block dump
===============
header address 221234268=0xd2fc45c
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 99
kdxcofbo 234=0xea
kdxcofeo 4692=0x1254
kdxcoavs 4458
kdxlespl 0
kdxlende 0
kdxlenxt 0=0x0
kdxleprv 4257529=0x40f6f9
kdxledsz 0
kdxlebksz 8032
row#0[7992] flag: ------, lock: 0, len=40
col 0; len 30; (30):
73 75 6e 2f 74 6f 6f 6c 73 2f 74 72 65 65 2f 53 77 69 74 63 68 53 74 61 74
65 6d 65 6e 74
col 1; len 6; (6): 00 40 f3 25 00 0a
row#1[7953] flag: ------, lock: 0, len=39
col 0; len 29; (29):
73 75 6e 2f 74 6f 6f 6c 73 2f 74 72 65 65 2f 54 68 69 73 45 78 70 72 65 73
73 69 6f 6e
col 1; len 6; (6): 00 40 f0 74 00 31
row#2[7914] flag: ------, lock: 0, len=39
col 0; len 29; (29):
73 75 6e 2f 74 6f 6f 6c 73 2f 74 72 65 65 2f 54 68 69 73 45 78 70 72 65 73
73 69 6f 6e www.2cto.com
col 1; len 6; (6): 00 40 f0 74 00 32
............................
............................
row#97[4727] flag: ------, lock: 0, len=35
col 0; len 25; (25):
79 43 62 43 72 53 75 62 53 61 6d 70 6c 69 6e 67 54 79 70 65 31 37 30 5f 54
col 1; len 6; (6): 00 40 f1 f1 00 0c
row#98[4692] flag: ------, lock: 0, len=35
col 0; len 25; (25):
79 43 62 43 72 53 75 62 53 61 6d 70 6c 69 6e 67 54 79 70 65 31 37 30 5f 54
col 1; len 6; (6): 00 40 f4 a2 00 10
----- end of leaf block dump -----
和分支节点不同的值解析如下：
kdxlespl 表示：当叶子节点被拆分时，未提交的事务数量
kdxlende 表示：被删除的索引条目数量
kdxlenxt 表示：当前叶子节点的下一个叶子节点的地址
kdxlprv 表示：当前叶子节点的上一个叶子节点的地址
kdxledsz 表示：被删除的空间
转储文件中接下来的部分就是索引条目部分。lock: 0 表示ITL中的锁信息 0表示没有被锁 ；len ：表示索引值长度 ；flag 表示 标记，如删除标记等。col 表示列号，从0开始 那么接下来就是索引的键值 以及 rowid中后三部分（相对文件号、块号、行号）即：col 0 是键值， col 1 是rowid。
也就是说，Leaf节点主要存储了完整的索引键值，以及相关索引键值的部分rowid(这个rowid去掉了data object number部分)，同时leaf 节点还存储了2个指针(DBA)，他们分别指向上一个leaf节点以及下一个leaf节点.这样叶子节点便是双向链表的结构。我们看到前面对B树索引的体系结构的描述，可以知道其为一个树状的立体结构。但对应到数据文件里的排列当然还是一个平面的形式，也就是像下面这样。因此，当oracle需要访问某个索引块的时候，势必会在这个结构上跳跃的移动。
www.2cto.com
/根/分支/分支/叶子/…/叶子/分支/叶子/叶子/…/叶子/分支/叶子/叶子/…/叶子/分支/.....
当oracle需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这般，最终访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到db
file sequential read等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。
1.前言：
动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树 (Red-Black Tree )，B-tree/B+-tree/
B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然对查找效率是有所提高的；还有一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。
这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，也就是这篇文章所要阐述的主题B~tree(B树结构)，B-tree这棵神奇的树是在Rudolf
Bayer, Edward M. McCreight(1970)写的一篇论文《Organization
and Maintenance of Large Ordered Indices》中首次提出。具体介绍可以参考wikipedia中的介绍：http://en.wikipedia.org/wiki/B-tree，其中还阐述了B-tree名字来源以及相关的开源地址。
在开始介绍B~tree之前，先了解下相关的硬件知识，才能很好的了解为什么需要B~tree这种外存数据结构。
2.外存储器—磁盘
计算机存储设备一般分为两种：内存储器(main memory)和外存储器(external
memory)。内存存取速度快，但容量小，价格昂贵，而且不能长期保存数据(在不通电情况下数据会消失)。
外存储器—磁盘是一种直接存取的存储设备(DASD)。它是以存取时间变化不大为特征的。可以直接存取任何字符组，且容量大、速度较其它外存设备更快。
2.1磁盘的构造
磁盘时一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片组成的盘组，每一盘片上有两个面。如下图6片盘组为例，除去最顶端和最底端的外侧面不存储数据之外，一共有10个面可以用来保存信息。
当磁盘驱动器执行读/写功能时。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读/写头(又叫磁头) 下通过时，就可以进行数据的读 / 写了。
一般磁盘分为固定头盘(磁头固定)和活动头盘。固定头盘的每一个磁道上都有独立的磁头，它是固定不动的，专门负责这一磁道上数据的读/写。
活动头盘 (如上图)的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的，因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装在同一个动臂上，因此不同盘面上的所有磁头都是同时移动的(行动整齐划一)。当盘片绕主轴旋转的时候，磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相同的磁道组成了一个圆柱面，我们称为柱面。因此，柱面的个数也就是盘面上的磁道数。
2.2磁盘的读/写原理和效率
磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)。
读/写磁盘上某一指定数据需要下面3个步骤：
(1) 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找。
(2) 如上图6盘组示意图中，所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。
(3) 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下。
经过上面三个步骤，指定数据的存储位置就被找到。这时就可以开始读/写操作了。
访问某一具体信息，由3部分时间组成：
● 查找时间(seek time) Ts: 完成上述步骤(1)所需要的时间。这部分时间代价最高，最大可达到0.1s左右。
● 等待时间(latency time) Tl: 完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快，一般为7200转/分(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种)。因此一般旋转一圈大约0.0083s。
● 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间，一般传输一个字节(byte)大概0.02us=2*10^(-8)s
磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts。
所以，在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(block)中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构，就是下面所要重点阐述的B-tree结构，以及相关的变种结构：B+-tree结构和B*-tree结构。
3.B-tree
B-tree又叫平衡多路查找树。一棵m阶的B-tree (m叉树)的特性如下：
（其中ceil(x)是一个取上限的函数）
1) 树中每个结点至多有m个孩子；
2) 除根结点和叶子结点外，其它每个结点至少有有ceil(m
/ 2)个孩子；
3) 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为null)；
5) 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)为关键字，且关键字按顺序排序K(i-1)<
Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： ceil(m
/ 2)-1 <= n <= m-1。
B-tree中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk
drives)的不同，一般块的大小在1k~4k左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查找的数据。
为了简单，这里用少量数据构造一棵3叉树的形式。上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件的内容在硬盘中的存储位置；p1表示指向17左子树的指针。
其结构可以简单定义为：
typedef struct {
/*文件数*/
int file_num;
/*文件名(key)*/
char * file_name[max_file_num];
/*指向子节点的指针*/
BTNode * BTptr[max_file_num+1];
/*文件在硬盘中的存储位置*/
FILE_HARD_ADDR offset[max_file_num];
}BTNode;
假如每个盘块可以正好存放一个B-tree的结点（正好存放2个文件名）。那么一个BTNode结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址。
模拟查找文件29的过程：
(1) 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】
(2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
(3) 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作2次】
(4) 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。
(5) 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】
(6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。
分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于3次磁盘IO操作时影响整个B-tree查找效率的决定因素。
当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘IO操作最少4次，最多5次。而且文件越多，B-tree比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。
上面仅仅介绍了对于B-tree这种结构的查找过程，还有树节点的插入与删除过程，以及相关的算法和代码的实现，将在以后的深入学习中给出相应的实例。
上面简单介绍了利用B-tree这种结构如何访问外存磁盘中的数据的情况，下面咱们通过另外一个实例来对这棵B-tree的插入（insert）,删除（delete）基本操作进行详细的介绍：
下面以一棵5阶B-tree实例进行讲解(如下图所示)：
其满足上述条件：除根结点和叶子结点外，其它每个结点至少有ceil(5/2)=3个孩子（至少2个关键字）；当然最多5个孩子（最多4个关键字）。下图中关键字为大写字母，顺序为字母升序。
结点定义如下：
typedef
