看懂执行计划之 B-Tree 索引

B-Tree 索引内部结构

B-Tree 是一种常见的数据结构，可以显著减少定位记录时所经历的中间过程，从而加快存取速度，主要用于 OLTP 系统（事务系统）。B-Tree 索引包含的主要组件如下：

根节点（Root Node）：一个 B-Tree 索引只有一个根节点，它实际就是位于树的最顶端的分支节点。
分支节点（Branch Node）：包含指向相应索引分支块或叶子块的指针和索引键值列。
叶子节点（Leaf Node）：包含被索引键值和该键值对应的 ROWID
索引项（Index Entry）：对应每一条行记录

分支节点（Branch Node）

分支节点主要包括两部分：指针和索引键值列。

指针
指针是指相关分支块或叶子块的块地址 RDBA。每个分支块都会有两种类型的指针，一种是 LMC（Left Most Child），比当前节点中最小的索引值还小的下一级节点块的数据块地址；另外一种是索引行记录指针即下一级节点块地址，该指针指向块的索引键值列最小值一定大于或等于该行记录的索引键值
索引键值列
索引键值列只要 Oracle 能区分相应的索引分支块或叶子块就行，这样既节省空间又可以快速定位下层的分支块或叶子块。

叶子节点（Leaf Node）

索引叶子节点也有两个指针，分别指向比当前节点最小索引值还小的叶节点块的地址，以及比当前节点最大索引值还大的叶节点块地址。通过这两个指针，把所有的叶节点串起来，形成一个双向链表。顺序遍历这个链表即可得到有序的数据。
拓展
唯一 B-Tree 索引，ROWID 存储在索引行的行头，Oracle 不存储该 ROWID 的长度，非唯一 B-Tree 索引则都需要存储。

B-Tree 索引优势

所有索引叶子块在同一层，访问每一个键值的时间相同
通过索引访问数据的时间是可控的、基本稳定
B-Tree 索引自动保持平衡
不会随着表数据量的增长而性能下降。

特别提醒
通过 B-Tree 索引访问数据的过程是先访问相关的 B-Tree 索引，然后再根据 ROWID 访问相应的行记录。
相应的会产生两部分消耗，一部分是访问索引的成本，另一部分是回表的成本。

访问 B-Tree 索引的方法

索引唯一扫描（INDEX UNIQUE SCAN）

WHERE 条件里是等值查询，扫描结果最多一条记录

索引范围扫描（INDEX RANGE SCAN）

WHERE 条件为范围查询，扫描结果可能返回多条记录。
同等条件下，当目标索引的索引行数量大于 1 时，索引范围扫描所消耗的逻辑读至少会比相应的索引唯一扫描的逻辑读多 1 因为范围扫描会扫描多个叶子块。

索引全扫描（INDEX FULL SCAN）

索引全扫描要从左至右依次顺序扫描目标索引所有叶子块的所有索引行，而索引是有序的，所以索引全扫描的执行结果也是有序的，并且是按照该索引的索引键值列来排序，这也意味着走索引全扫描能够既达到排序的效果，又同时避免了对该索引的索引键值列的真正排序操作。

NULL 值不会在 B 树索引中存在，这意味着 Oracle 中能做索引全扫描的前提条件是目标索引至少有一个索引键值列的属性是 NOT NULL

索引快速全扫描（INDEX FAST FULL SCAN）

从段头开始，读取包含位图块，root block, 所有的 branch block, leaf block，读取的顺序完全由物理存储位置决定，并采取多块读，每次读取 db_file_multiblock_read_count 个。

索引快速全扫描与索引全扫描的区别

索引快速全扫描只适用于 CBO
索引快速全扫描可以使用多块读，也可以并行执行
索引快速全扫描的执行结果不一定是有序的
索引快速全扫描是根据索引行在磁盘上的物理存储顺序来扫描
索引全扫描时按照逻辑顺序从左至右依次扫描
对于单个索引叶子块中的索引行而言，其物理存储顺序和逻辑存储顺序一致;但对于物理存储位置相邻的索引叶子块而言，块与块之间索引行的物理存储顺序则不一定在逻辑上有序

索引跳跃式扫描（INDEX SKIP SCAN）

索引跳跃式扫描使那些在 where 条件中没有对目标索引的前导列指定查询条件但同时又对该索引的非前导列指定了查询条件的目标 SQL 依然可以用上该索引。Oracle 会对该索引的前导列的所有 distinct 值做遍历，然后对原目标 SQL 做等价改写，将目标列的所有前导列的 distinct 值加进来。

Oracle 中的索引跳跃式扫描仅仅适用于那些目标索引前导列的 distinct 值数量较少、后续非前导列的可选择性又非常好的情形，因为索引跳跃式扫描的执行效率一定会随着目标索引前导列的 distinct 值数量的递增而递减。