Oracle B*树索引

 

       B*树索引就是我们说的“传统”索引，这是数据库中最常用的一类索引结构。其实现与二叉查找树类似，目标是减少oracle查找数据的时间。如果在一个数字列上有一个索引，那么理论上结构应该是这样的：

        这个树最底层是叶子节点，包含索引键以及一个rowid（指向索引行）。叶子节点上面的称为分支块，用于在结构中实现导航。例如：想在索引中找到值42，从树顶开始查找，进入左分支，查找这个块，发现需要找的数据在“42...50”的叶子节点中。

        另外，叶子节点之间是双向链表结构。也就是查找区间数据很容易，比如这样的条件，where x between 20 and 300。oracle只要刚开始找到大于或等于20的记录所在的叶子节点，接着往下扫描，找到大于或者等于300的块。这期间可能会跨叶子节点扫描，由于叶子节点之间是双向链表，故很容易实现跨叶子节点扫描。

       B*树有一个特点：所有的叶子节点都在同一层，也就是无论你查找哪一条数据，需要执行的I/O数据是一样的。一般的B*树都是2或者3层。无论这个表有多少行数据，这样查找一条数据只需要2,3个I/O操作。

 

      索引键压缩

      假如一个表中，需要三列才能确认一行。那么我们在这个表示建立索引需要建立在这三列上。那么索引块的结构有可能是这样的，

                               
       我们会发现，第一列和第二列有很多值是重复的。其实这个时候可以进行压缩，对于重复的值，只保存一份。比如：

 

drop index t_idx;
create index t_idx on
t(owner,object_type,object_name)
compress &2;

       compress&2表示压缩两列，这样能节省空间，但是会增加寻找的难度。也就是说，如果现在已经占用了大量的cpu时间，那么创建索引以压缩的方式，会使情况更糟糕。如果目前只是I/O操作比较多，那么压缩索引能加快处理速度，因为压缩之后的索引空间更少，那么块缓冲区应该能存放更多的索引块，块的命中率会提高。

 

      反向键索引

      假如我们建立的所有是在一个递增的列上，从上面的图1索引结构图，可以看出，相邻的值保存在同一索引块上。那么我们批量递增插入数据的时候，就会引起索引块的竞争。但是如果我们把索引值反转之后，原先相邻的值，就会相差很远，这样就降低了索引块的竞争。

      反向索引有一个缺点，无法进行区间扫描。因为索引值已经反转，索引值相邻的值都是反转之后相邻的值，实际值其实相差很远，区间扫描无法进行。

      那么，假设我们需要一个表，有一个主键是递增的，而且今后也不会在这个主键上进行区间扫描。但是有大批量的插入，这个时候就适合建立一个反向键索引。

 

      B*树使用情况

      什么时候应该使用B*树索引，什么时候又不行呢？主要看两点：

      1. 当需要通过索引访问表中很少一部分数据的时候，可以建立B*树索引。

      2. 即使需要访问表中多行，但是能只访问索引解决，也可以建立B*树索引。比如select count(*) from ...。

 

      为什么只有访问少量数据的时候，才能使用B*树索引呢，举一例子：

      假设我们通过索引读取一个表，而且要读取表中20%的行。若这个表中有100,000行，其中的20%就是20,000行。如果行大小约为80字节，在一个块大小为8KB的数据库中，每个块上则有大约100行。这说明，这个表有大约1000个块。了解了执行情况，计算起来就非常容易了。我们要通过索引读取20,000行；这说明，大约是20,000个TABLE ACCESS BY ROWID操作。为此要处理20,000个表块来执行这个查询。不过，整个表才有大约1000个块！最后会把表中的每一个块读取好处理20次。即使把行的大小提高一个数量级，达到每行800字节，这样每块有11.行，现在表中就有11.,000个块。要通过索引访问20,000行，仍要求我们把每一个块平均读取2次。还没有全表扫描块，全表扫描每一块只需访问一次。

 

      物理组织

      数据在磁盘上如何物理地组织，对上述例子有显著影响。如果那个索引的主键是按递增的方式存储在磁盘，那么上述例子的情况完全会不同，读取2W行数据完全不需要读取2W次块。读取一次块，即把这一块的数据读取到了缓存，这一块上符合条件的数据有很多，可能基本上都是想要的，那么相当于读一次块就读到了100行数据，我们需要2W行数据，那么读取200次块左右，而不是上述例子中的2W次块。上述例子是极限情况，上行数据和下一行数据都不在同一块上。

       刚刚说的，读一次块就读了100行到缓存，其实有一个前提条件，前提是设置一个参数为100,。到oracle块读取数据的时候，有一个参数，代表一次读取多少行，叫做ARRAYSIZE。在java/jdbc中，connect或者statement对象有一个prefetch方法,代表一次读取多少行。假设设置成100，读取第一行的时候找到第一行所在的数据块读取，接着就开始读取第二行，这个时候发现第二行也在这个块上，于是直接就取了。接着就读取剩下的98行，直到读完100行数据。假设100行都在这个块上，那么只有一次I/O操作。也就是上面所说的一次读取了100行到缓存。但是假设那个参数设置的是10，那么相当于要读取10次，也就是同一个块要读取10次，才能获得100行数据。可见这个参数的设置是相当重要的。