转载

浅谈索引系列之基本原理

注意：本文谈论的索引仅限最常用的标准B*Tree索引，位图索引，聚簇索引不在本文讨论范围内，以下原理并不适用。
关于索引前段时间已经写了浅谈索引序列之是否可以存储NULL值？浅谈索引系列之聚簇因子(clustering_factor)两篇博文，之所以再返回来写基本原理是因为发现自己对索引的基本原理了解的并不是很深入，翻阅了相关资料后整理了几个索引的重要知识点如下，和大家共享。
    1.B*Tree索引中索引条目是按照键值排序存储的。
    2.B*Tree索引存储空间可以进行预先估算。
    3.叶子节点之间相互指向，在结合1,因此索引条目按照键值构成了一个双向有序链表
下面通过具体的例子进行说明：

索引键值顺序

创建测试表和索引

点击(此处)折叠或打开

drop table test;
create table test as select * from all_objects order by OBJECT_NAME;
create index test_pk on test(object_id);

对索引进行treedump,为了便于阅读关于treedump方法请参考浅谈索引序列之是否可以存储NULL值？博文，取trace日志中任一叶子节点进行查看
leaf: 0x1002ff8 16789496 (3: nrow: 479 rrow: 479)

点击(此处)折叠或打开

SQL> SELECT dbms_utility.data_block_address_file(16789496),dbms_utility.data_block_address_block(16789496) FROM dual;
DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(16789496) DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(16789496)
---------------------------------------------- -----------------------------------------------
4 12280
SQL> alter system dump datafile 4 block 12280;

打开dump出来的trace文件，限于篇幅只截取部分，可以清晰的看到虽然表是按照OBJECT_NAME的依次插入记录的，但是索引条目依然按照OBJECT_ID的顺序存储在块中。
row#0[8019] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 58
col 1; len 6; (6): 01 00 2f bb 00 19
row#1[8006] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 59
col 1; len 6; (6): 01 00 2f c2 00 43
row#2[7993] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5a
col 1; len 6; (6): 01 00 2f bb 00 17
row#3[7980] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5b
col 1; len 6; (6): 01 00 2f c2 00 47
row#4[7967] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5c
col 1; len 6; (6): 01 00 2f bb 00 1b
row#5[7954] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5d
col 1; len 6; (6): 01 00 2f c2 00 49

...
那么我们看看再次插入OBJECT_ID=2088的记录效果怎么样?

点击(此处)折叠或打开

SQL> insert into test select * from dba_objects where object_id=2088;
1 row created.
SQL> commit;
Commit complete.
SQL> alter system dump datafile 4 block 12280;
System altered.

row#0[8019] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 58
col 1; len 6; (6): 01 00 2f bb 00 19
row#1[8006] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 59
col 1; len 6; (6): 01 00 2f c2 00 43
row#2[1797] flag: ------, lock: 2, len=13
col 0; len 3; (3): c2 15 59
col 1; len 6; (6): 01 00 30 6b 00 00
row#3[7993] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5a
col 1; len 6; (6): 01 00 2f bb 00 17
row#4[7980] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5b
col 1; len 6; (6): 01 00 2f c2 00 47
row#5[7967] flag: ------, lock: 0, len=13
col 0; len 3; (3): c2 15 5c
col 1; len 6; (6): 01 00 2f bb 00 1b

发现了什么？索引中新增了一键值为c2 15 59（2088）的索引条目。无论记录在表中是怎么杂乱无章存储的还是按照有序的，一旦创建索引后，索引条目都是按照索引列为顺序来进行存储的，这里就引出了聚簇因子概念，具体聚簇因子的概念在这里不再赘述。另外执行计划中INDEX FULL SCAN也是基于索引键值有序这个原理。

存储空间估算

生产环境任何操作都可能存在隐患，导致业务无法正常对外服务。创建索引也不例外，如何预先评估索引占用的空间，防止表空间被占满可能是每位DBA必备的技能，下面将结合索引条目的结构来说明一下索引的占用情况。
叶子节点索引条目的数据结构如下：
浅谈索引系列之基本原理

分支节点索引条目的数据结构如下：
浅谈索引系列之基本原理

对于默认段，其缺省的PCTFREE为10%,也就是说最多只能使用其中的90%,因此对于一个大小为8K的块来说仅有8192*90%=7372.8字节可用。
1.首先计算出每个叶子节点索引条目占用的字节数byte_per_lnode，7372.8/byte_per_lnode进而计算出每个叶子节点保存多少索引条目entries_per_lnode,表的总行数total_num/entries_per_lnode得到叶子节点的总个数lnodes，因此叶子节点占用的总空间为:lnodes*8k
2.计算出每个分支节点索引条目占用的字节数byte_per_bnode，7372.8/byte_per_bnode进而计算出每个分支节点保存多少索引条目entries_per_bnode,用步骤1中lnodes/byte_per_bnode得到分支节点的总个数bnodes,因此最底层分支节点占用的总空间为bnodes*8k
3.检查分支节点总个数是否超过了byte_per_bnode,如果大于byte_per_bnode说明至少还有两层分支节点，需要再重复步骤2的情况。否则计算空间完成。
因此索引占用的存储空间为：lnodes*8k+bnodes*8k,注意存储空间的大小仅为估算，加上一小部分管理空间，实际占用空间可能会比预算空间大一些。

双向有序链表

在trace出索引叶子块的信息后，有如下关键字
kdxlenxt 16789497=0x1002ff9
kdxleprv 16789495=0x1002ff7
其中kdxlenxt为下一个叶子节点的地址，kdxleprv为上一个叶子节点的地址。每个叶子节点都有此信息标记了上一个以及下一个叶子节点的信息，因此叶子节点构成了一个索引键值有序的双向有序链表，这种有序结构某些情况下避免了再次排序，节省了oracle的硬件资源，提高了效率。

正文到此结束