Oracle 使用平衡树（Btree）存储索引以便提升数据访问速度当不使用索引时用户必须对数据进行顺序扫描（sequential scan）来查找指定的值如果有 n 行数据那么平均需要扫描的行为 n/因此当数据量增长时这种方法的开销将显着增长
如果将一个已排序的值列（list of the values）划分为多个区间（range）每个区间的末尾包含指向下个区间的指针（pointer）而搜索树（search tree）中则保存指向每个区间的指针此时在 n 行数据中查询一个值所需的时间为 log(n)这就是 Oracle 索引的基本原理
下图显示了平衡树索引（Btree index）的结构
在一个平衡树索引（Btree index）中最底层的索引块（叶块（leaf block））存储了被索引的数据值以及对应的 rowid叶块之间以双向链表的形式相互连接位于叶块之上的索引块被称为分支块分枝块中包含了指向下层索引块的指针如果被索引的列存储的是字符数据那么索引值为这些字符数据在当前数据库字符集中的二进制值
对于唯一索引每个索引值对应着唯一的一个 rowid对于非唯一索引每个索引值对应着多个已排序的 rowid因此在非唯一索引中索引数据是按照索引键（index key）及 rowid 共同排序的键值（key value）全部为 NULL 的行不会被索引只有位图索引（bitmap index）和簇索引（cluster index）例外在数据表中如果两个数据行的全部键值都为 NULL也不会与唯一索引相沖突
有两种类型的索引块
用于搜索的分支块（branch block）
用于存储索引数据的叶块（leaf block）
分支块中存储以下信息
最小的键值前缀用于在（本块的）两个键值之间做出分支选择
指向包含所查找键值的子块的指针
包含 n 个键值的分支块含有 n+ 个指针键值及指针的数量同时还受索引块容量的限制
所有叶块相对于其根分支块的深度是相同的
叶块用于存储以下信息
数据行的键值（key value）
键值对应数据行的 ROWID
所有的 键值ROWID 对都与其左右的兄弟节点向链接并按照（keyROWID）的顺序排序
平衡树数据结构（Btree structure）具有以下优势
平衡树（Btree）内所有叶块的深度相同因此获取索引内任何位置的数据所需的时间大致相同
平衡树索引（Btree index）能够自动保持平
平衡树内的所有块的使用容量平均在块总容量的 / 左右
在大区间范围内进行查询时无论匹配个别值还是搜索一个区间平衡树都能提供较好的查询性能
数据插入（insert）更新（update）及删除（delete）的效率较高且易于维护键值的顺序
大型表小型表利用平衡树进行搜索的效率都较好且搜索效率不会因数据增长而降低
