共计 4205 个字符，预计需要花费 11 分钟才能阅读完成。
今天研究下 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 索引的结构如下图：
每个节点占用一个磁盘块的磁盘空间，一个节点上有 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 的索引组织表）
二级索引：存储索引列值 + 主键信息
总结：
索引能提高检索数据的效率，但是索引的建立必须慎重，对每个索引的必要性都应该经过仔细分析，要有建立的依据。因为太多的索引与不充分、不正确的索引对性能都毫无益处：在表上建立的每个索引都会增加存储开销，索引对于插入、删除、更新操作也会增加处理上的开销。另外，过多的复合索引，在有单字段索引的情况下，一般都是没有存在价值的；相反，还会降低数据增加删除时的性能，特别是对频繁更新的表来说，负面影响更大。
更多 Oracle 相关信息见Oracle 专题页面 http://www.linuxidc.com/topicnews.aspx?tid=12
本文永久更新链接地址：http://www.linuxidc.com/Linux/2018-01/150649.htm
