转载

oracle btree索引概述

今天研究下oracle的btree索引，通过这篇文章你会了解到，oracle btree索引都有哪几种类型、oracle btree索引的实现原理，oracle通过btree索引检索数据的过程、以及b*tree索引的限制，并且oracle和mysql的btree索引的区别。

一：oracle中 btree索引的子类型:

b*tree索引是oracle乃至大部分其他数据库中最常用的索引，b*tree的构造类似于二叉树，但是这里的“B”不代表二叉（binary），而代表平衡（balanced),b*tree索引有以下子类型：

1）索引组织表（index organized table): 索引组织表以B*树结构存储，我们知道oracle默认的表是是堆表，堆表是以一种无组织的方式存储的（只要有可用的空间，就可以放数据），而IOT与之不同，IOT中的数据按着主键的顺序存储和排序的，对于应用来说，IOT表现得和常规的堆表并无区别，需要使用sql来正确的来访问IOT, IOT对信息获取、空间系统和OLAP应用最为有用，简单的概述起来：索引组织表----索引就是数据，数据就是索引，因为数据就是按着B*树结构存储的。

2）b*tree聚簇索引（B*tree cluster index):基于聚簇键（如 age=27），在传统的btree索引中，键都指向一行，而B*树聚簇不同，一个聚簇键会指向一个块，其中包含与这个聚簇键相关的多行，

3)降序索引：允许数据在索引结构中按“从大到小”的顺序（降序）排序，而不是“从小到大的顺序（升序）排序，当你查询数据的时候，最后排序oder by A desc,B asc的时候，创建降序索引就能避免做昂贵的排序（sort order by ）操作，如下语句创建：

SQL>create index idex_name on table_name(A desc,B asc);

4)反向键索引（reverse key index):这也是 btree索引，只不过键的字节会“反转”，利用反向键索引，如果索引中填充的是递增的值，索引条目在索引中可以得到更均匀的分布；主要是解决“右侧”索引叶子块的竞争，比如在一个oracle RAC的环境中，某些列用一个序列值或者时间戳填充，这些列上建立索引就属于“右侧”索引，也就是数据分布的相对比较集中。使用反向索引最大的优点莫过于降低索引叶子块的争用，减少索引热点块，提高系统性能。

1.反向索引应用场合

1）发现索引叶块成为热点块时使用

通常，使用数据时（常见于批量插入操作）都比较集中在一个连续的数据范围内，那么在使用正常的索引时就很容易发生索引叶子块过热的现象，严重时将会导致系统性能下降。

2）在RAC环境中使用

当RAC环境中几个节点访问数据的特点是集中和密集，索引热点块发生的几率就会很高。如果系统对范围检索要求不是很高的情况下可以考虑使用反向索引技术来提高系统的性能。因此该技术多见于RAC环境，它可以显著的降低索引块的争用。

2.使用反向索引的缺点

由于反向索引结构自身的特点，如果系统中经常使用范围扫描进行读取数据的话（例如在where子句中使用“between and”语句或比较运算符“>”“<”等），那么反向索引将不适用，因为此时会出现大量的全表扫描的现象，反而会降低系统的性能。

二：oracle中BTree索引的实现原理：一个经典的BTree索引的结构如下图：
oracle btree索引概述

每个节点占用一个磁盘块的磁盘空间，一个节点上有n个升序排序的关键字和（n+1)个指向子树根节点的指针（上图中关键字为51,101,151.。。。。，然后0到50 对应一个指针，51到100对应一个指针），这个指针存储的是子节点所在磁盘块的地址（注意这里的n是创建索引的时候，根据数据量计算出来的，如果数据量太大了，三层的可能就满足不了，就需要四层的B+tree）,然后n个关键字划分成（n+1)个范围域，然后每个范围域对应一个指针，来指向子节点，子节点又从新根据关键字再次划分，然后指针指向叶子节点，并且所有的叶子节点都在树的同一层上，这说明所有的从索引根节点到叶子节点的遍历都会访问同样数目的块，也就是说会执行同样数目的I/O,换言之索引是高度平衡的，

上图就是 0...50对应一个指针，指向一个子节点；51...100对应一个指针，指向另一个子节点，然后子节点又根据关键字划分区域，并由指针指向叶子结点，值得注意的是oracle B*树索引存数据的是叶子节点（或者叫叶子块）；存的是索引键值（或者叫索引的列值)和一个rowid(指向所索引的行的一个指针或者说叫物理位置），然后如上图所示，叶子节点之间有双向链表，就是为了提高索引范围扫描的效率，因为索引值的列值是有序的，找到了起始值后，直接就可以有序的去相邻中找到下一个值，例如 where id between 10 and 20 ,oracle 发现第一个最小键值大于或等于10的索引叶子块，然后水平地遍历叶子节点链表，直到最后一个大于20的值；

需要注意的是：B*索引中不存在非唯一限制，也就是说非唯一列上也可以创建B*索引，但是在一个非唯一索引中，oracle会把rowid作为一个额外的列（有一个长度字节）追加到键上，使得键唯一，例如有一个create index index_name on table( x ,y)索引，从概念上说，他就是create unique index index_name on table( x ,y,rowid).在一个唯一索引中，根据你定义的唯一性，oracle 不会再向索引键增加rowid,在非唯一索引中，你会发现，数据会首先按索引键值排序，然后按rowid升序排序，而在唯一索引中，数据只按着索引键值排序；

三：使用B*树索引检索数据的过程。

针对下图B+tree索引的原理（修改自网络）：

然后针对上图模拟下 where id=29的具体过程：。

首先根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

比较关键字29在区间（17,35），找到磁盘块1的指针P2。

根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】

比较关键字29在区间（26,30），找到磁盘块3的指针P2。

根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】

在磁盘块8中的关键字列表中找到关键字29。

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。

四：oracleb*tree索引的限制

1）在索引列上使用函数。如SUBSTR,DECODE,INSTR等，对索引列进行运算.需要建立函数索引就可以解决了。

例如：表dept，有col_1,col_2,现在对col_1做upper函数索引如下：

CREATE INDEX index_name ON dept(upper(col_1));

函数索引是基于代价的优化方式-CBO，（在Oracle8及以后的版本,Oracle强列推荐用CBO的方式，而非RBO）,所以表必须经过analyze才可以使用，或者使用hints才可以；

2）新建的表还没来得及生成统计信息，分析一下就好了，我们知道oracle优化器是基于统计信息来判断执行计划的，如果统计信息不准确，那么oracle可能会做出不走索引的执行计划。

3）oracle优化器cbo是基于cost的成本分析，访问的表过小，使用全表扫描的消耗小于使用索引。

4）使用<>、not in 、not exist，对于这三种情况中大多数情况下认为结果集很大，一般大于5%-15%就不走索引而走全表扫描（FTS)。

5) like "%_" 百分号在前。

6) 单独引用复合索引里非第一位置的索引列,oracle和mysql一样，btree索引都是最左匹配原则，当你创建组合索引（A，B，C）相当于创建了(A)、 (A,B)、（A，B，C)三个索引；

7）字符型字段为数字时在where条件里不添加引号，这里oracle内部使用函数做隐士转换，所以可以归结为第一类，使用函数导致索引失效，值得注意的是：VARCHAR2->NUMBER的隐式转换，可以走索引；NUMBER->VARCHAR2的隐式转换，就导致索引失效了。（VARCHAR2->NUMBER不会让索引失效，可以理解成转换为where id = to_number('123')。NUMBER->VARCHAR2会让索引失效，我猜测是转换为where to_number(name) = 123）

8）当变量采用的是times变量，而表的字段采用的是date变量时.或相反情况。

9)索引失效（INVALID)，可以考虑重建索引，alter　index　index_name rebuild online;。

10)B-tree索引 is null不会走,is not null会走;

五：oracle和mysql的btree索引的区别

其实oracle和mysql的btree索引结构和原理很相似，只是oracle叶子节点存储的是键值+rowid，mysql的索引叶子结点存储的内容因存储引擎不同而不同，还有主键索引和二级索引之分如下：

oracle叶子节点存储的是键值+rowid

MyISAM引擎中leaf node存储的内容:

主键索引：仅仅存储行指针；

二级索引：仅仅是行指针；

InnoDB引擎中leaf node存储的内容

主键索引：聚集索引存储完整的数据（整行数据）（类似于oracle的索引组织表）

二级索引：存储索引列值+主键信息
总结：

索引能提高检索数据的效率，但是索引的建立必须慎重，对每个索引的必要性都应该经过仔细分析，要有建立的依据。因为太多的索引与不充分、不正确的索引对性能都毫无益处：在表上建立的每个索引都会增加存储开销，索引对于插入、删除、更新操作也会增加处理上的开销。另外，过多的复合索引，在有单字段索引的情况下，一般都是没有存在价值的；相反，还会降低数据增加删除时的性能，特别是对频繁更新的表来说，负面影响更大。

正文到此结束