（转）深入研究B树目录（三、四）

（转）深入研究B树索引（三、四）

3.????B树索引的访问

?

我们已经知道了B树索引的体系结构，那么当oracle需要访问索引里的某个索引条目时，oracle是如何找

第一种方式则是访问索引里的数据块，而第二种方式的I/O操作属于全表扫描。这里顺带有一个问题，为

我们看到前面对B树索引的体系结构的描述，可以知道其为一个树状的立体结构。其对应到数据文件里的

当oracle需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这般，最终访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到db file sequential read等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。

那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时，oracle知道要访问所有的数据块，因此唯一的问题就是尽可能高效的访问这些数据块。因此，这时oracle可以采用同步的方式，分几批，同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的，因此其对应到db file scattered read等待事件。

?

4.????B树索引的管理机制

4.1 B树索引的对于插入（INSERT）的管理

对于B树索引的插入情况的描述，可以分为两种情况：一种是在一个已经充满了数据的表上创建索引时，

我们来做个试验看看这个过程。我们先试着插入插入10条记录。注意，对于2KB的索引块同时PCTFREE为缺省的10％来说，只能使用其中大约1623字节（2048×90％×88％）。对于表index_test来说，叶子节点中的每个索引条目所占的空间大约为161个字节（3个字节行头+1个字节列长+150个字节列本身+1个字节列长+6个字节ROWID），那么当我们插入将10条记录以后，将消耗掉大约1610个字节。
在打开跟踪文件之前，我们先来看看表index_test里存放了哪些数据。????
打开419块的跟踪文件可以发现，里面存放了10、12、14、16、18、20、22、24和2a；而420块的跟踪文件中记录了4a、6a和8a。也就是说，由于最后我们插入24的缘故，导致整个叶子节点发生分裂，从而将10、12、14、16、18、20、22、和2a放到419块里，而4a、6a和8a则放入420块里。然后，再将新的索引条目（24）插入对应的索引块里，也就是419块。

假如我们再最后不是插入12*2，而是插入9会怎么样？我们重新测试一下，返回到index_test里有11条记录的情况下，然后我们再插入9。

如果这时，我们再次插入12*2，则会发现419号节点的分裂过程和前面描述的一样，会将原来放在419块里的4a、6a和8a放入一个新的叶子节点里（421块），然后将12*2放入419块，于是这个时候419块所含有的索引条目为10、12、14、16、18、20、22、和2a。同时420块没有发生变化。

从上面有关叶子节点分裂的过程可以看出，其过程是非常复杂的。因此如果发生的是第二种情况，则为了

因此，这时的索引层次就变成了2层。同时可以看出，根节点索引块在物理上始终都是同一个索引块。而

当数据量再次不断增加，导致原来的根节点不足以存放新的索引条目（这些索引条目指向分支节点）时，

再次引起根节点的分裂，其分裂过程与前面所说的由于叶子节点的增加而导致的根节点分裂的过程是一样的。

同时，根节点分裂以后，索引的层级再次递增。由此可以看出，根据B树索引的分裂机制，一个B树索引始终都是平衡的。注意，这里的平衡是指每个叶子节点与根节点的距离都是相同的。同时，从索引的分裂机制可以看出，当插入的键值始终都是增大的时候，索引总是向右扩展；而当插入的键值始终都是减小的时候，索引则总是向左扩展。