Oracle 使用平衡树（B tree）存储索引以便提升数据访问速度 当不使用索引时 用户必须对数据进行顺序扫描（sequential scan）来查找指定的值 如果有 n 行数据 那么平均需要扫描的行为 n/ 因此当数据量增长时 这种方法的开销将显著增长
如果将一个已排序的值列（list of the values）划分为多个区间（range） 每个区间的末尾包含指向下个区间的指针（pointer） 而搜索树（search tree）中则保存指向每个区间的指针 此时在 n 行数据中查询一个值所需的时间为 log(n) 这就是 Oracle 索引的基本原理
下图显示了平衡树索引（B tree index）的结构
在一个平衡树索引（B tree 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 对都与其左右的兄弟节点向链接 并按照（key ROWID）的顺序排序
平衡树数据结构（B tree structure）具有以下优势
平衡树（B tree）内所有叶块的深度相同 因此获取索引内任何位置的数据所需的时间大致相同
平衡树索引（B tree index）能够自动保持平
平衡树内的所有块的使用容量平均在块总容量的 / 左右
在大区间范围内进行查询时 无论匹配个别值还是搜索一个区间 平衡树都能提供较好的查询性能
数据插入（insert） 更新（update） 及删除（delete）的效率较高 且易于维护键值的顺序
lishixinzhi/Article/program/Oracle/201311/16672