2.2 索引与排序

通过2.1节的介绍,我们知道了索引扫描是可以优化排序的,索引扫描输出的结果是有序排列的(索引快速全扫描除外),为什么会这样呢,难道索引输出的时候自动做了一次排序吗?其实不是的,应该说索引本身就是一种有序排列的数据结构。索引在建立条目的时候,就已经将其按照索引列的顺序进行顺序存储,这和表的存储结构是不一样的。

之所以将排序这个话题单拿出来讲,主要是为了说明一个排序的道理。很多人可能有意无意地会忽略了SQL语句中的排序这块,其实很多时候,避免排序可以大大提升SQL语句的性能,这是非常重要的一点。不论作为开发者还是管理者,都需要时刻保持对排序的敏感。很多时候,临时表空间使用率超限,查询速度太慢都可能是因为排序太多,PGA内存排序区装不下,不得不放到临时表空间去排序,临时表空间是磁盘排序,在速度上和内存排序是无法比拟的。

本节将围绕索引这种有序结构与排序优化展开介绍,让读者充分了解到索引对优化排序的作用。

2.2.1 B树索引内部结构

我们已经了解到了B树索引是一种典型的树形结构,其包含的组件主要是:

q  根节点:只有一个根节点,是位于树的最顶端的分支节点。

q  分支节点:存储指针指向索引里其他的分支节点或者叶节点。

q  叶子节点:存储索引条目(包括:索引条目头信息、索引键值长度、索引键值,以及ROWID相关信息)直接指向表里的数据行。

下面通过一张示意图来描述一下这种内部结构,如图2-6所示,就分支节点块(包括根节点块)来说,其所包含的索引条目都是按照顺序排列的(默认是ASC升序排列,也可以在创建索引时指定为DESC降序排列)。每个索引条目均由两个字段组成,第一个字段表示当前该分支节点块下所指向的叶节点块中所包含的开始键值(对升序排序的索引来说,就是最小键值),第二个字段为指向叶节点块地址的指针。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。在本例中,对于根节点块来说,包含三个指针,分别为(1 B1)、(100 B2)、(200 B3),它们指向三个分支节点块。其中的1、100和200分别表示这三个分支节点块所指向的开始键值,而B1、B2和B3则表示所指向的三个分支节点块的地址。

对于叶子节点块来说,其所包含的索引条目与分支节点一样,都是按照顺序排列的。每个索引条目也包含两个字段。第一个字段表示索引的键值,对于单列索引来说是一个值,而对于复合索引来说则是多个值组合在一起的,第二个字段表示该键值所对应的数据行的ROWID,该ROWID是数据行在表里的物理地址。

 book_ch02_06

图2-6  B树索引内部结构

 

当有新的索引键值插入的时候,索引会判断新键值的排序位置,如果新键值大于目前索引存储的最大值,则会将新键值插入到最右侧的叶节点块(L8)上,如果新键值为198,则会将其插入到节点块L6上。如果对应叶节点块已满,则会分裂出新的叶节点块,分支节点块满了,同样会分裂出新块。

索引这个特点是不同于表的,DML操作过程中,对索引维护成本是比较大的,所以我们需要定期地去分析索引的结构,保证其高效支持查询的能力。

 

Trackback

no comment untill now

Add your comment now

切换到手机版