本文翻译自Jonathan Lewis早年写在dbazine上的文章unbalanced indexes? 本文的word版本可以到此处下载

原文参见: 不平衡的索引?

不平衡的索引?
by Jonathan Lewis

网络上有多篇介绍Oracle索引实现机制的文章,都提及需要经常重建索引.在这些文章中的某处,总是会出现这样一段简短的描述,索引会如何变的不平衡,以及可能导致的后果.很不幸,它们好像忽视了这样一个事实,Oracle使用的B-tree机制是一种”平衡B-tree”索引,也就是说,索引无法变得不平衡.

“平衡”到底意味着什么?

既然Oracle的索引使用的是平衡B-tree,为什么还有如此多的人相信他们的索引会变得不平衡呢?
另外,平衡B-tree到底又是什么呢?
第二个问题的答案可能能够帮助我们得到第一个问题的答案.
从技术角度讲,平衡B-tree的显要特性是,在任意时间点,任何叶子节点(leaf block)到根节点(root block)的距离都相等,平衡是指从顶部到底部的平衡.
就Oracle来说,执行一个treedump命令就可以很容易发现这一点,如图-1所示:

select	object_id
from	user_objects
where	object_type = 'INDEX'
and	object_name = 'T1_IDX1'
-- and 	subobject_name = . . .
;
alter session set events '
'immediate trace name treedump level N';

图-1: 一次索引树转储涉及到的步骤

首先,需要找到你想要转储(dump)索引或者索引分区(index partition)的object_id;接着,将object_id作为level的参数来调用treedump事件. 如果检查这个索引树(tree dump)转储生成的跟踪文件,你将发现类似于图-2中所示的结果.

branch: 0x14001aa 20971946 (.. level 2)
  branch: 0x14003ef 20972527 (.. level 1)
    leaf: 0x14001ab 20971947 (..)
    leaf: 0x14001ac 20971948 (..)

图-2: 从索引树转储结果中提取出的一段内容

这个跟踪文件以递归降序的方式展示索引的分支块(branch block,根块只是分支块的一个特例)与叶子块.注意,转储内容的第一个块(根块)记录了一个高度(level),并且它下面的每一个分支块也都记录了一个高度,但是叶子块没有记录高度.
根块的高度就是索引的blevel(执行analyze index命令之后会记录在视图dba_indexes中).索引的高度(height,执行命令validate index后会记录在视图index_stats中)就是blevel + 1.
每一个叶子块到根块的距离就正好有这么多步.索引总是平衡的.
那么为什么有那么多人相信Oracle会允许索引变得不平衡呢?

我应负的责任

此时,我必须承认我有罪,仅仅在一年前(2002年5月),我也重复了一个关于块分裂(index block split)的众所周知但是却完全错误的描述.虽然我知悉(在我的书(2000年12月,Practical Oracle 8i)中对此做了说明) treedump的细节,但我还是这样做了.
我猜想,这种错误的观念最初产生于Oracle5(很多年以前)手册的说明,其大意是,因为”没有一个叶子块到根块的距离比任何其他叶子块到根块的距离远.”, 所以Oracle索引是平衡的.将这个表述与一个过于简化的块分裂的图结合到一起,瞧,一个几乎牢不可破的神话就诞生了.
图-3和图-4描绘了一个非常常见,但是完全错误的关于叶子块如何分裂的概念.

图-3: 叶子块将要分裂前的索引结构

图-4 这不是叶子块分裂发生的方式

有这样一个流传广泛的说法,叶子块分裂到两个全新的块,这两个块分享它的所有数据;接着, Oracle在原来的叶子块的位置插入一个新的分支块来持有指向这两个块的指针.因此,在这样一个错误的视角下,这个索引的右边就会比左边更深.(经常会有人说,创建在基于序列的字段上的索引会带来最大的问题,因为,从这个理论来推导,最右边的叶子块到根块的距离会越来越远,没分裂一次,就会降低一层.)
事实上,这个工作Oracle做得更加精致前瞻并有效得多. 图-5所示是一个复杂的叶子块分裂的结果.

图-5: 一次递归分裂后的索引结构图
由于这个叶子块分裂成了两个块,Oracle会尝试往当前指向这个叶子块的分支块中插入一个额外的指针.
但是,如果这个分支块也满了,Oracle会继续将这个分支块也分裂成两个块,并且在两个分支块之间分配现存块里的指向叶子块的指针,并且(递归地) 在这个分支块的上一级的分支块中插入一个指向这个新的分支块的新的分支指针.
如果在这个过程中,Oracle抵达了根块,然而这个根块也满了,那么根块也必须分裂.在这种情况下,Oracle将创建一个新的根块来持有这两个分支指针.(事实上,Oracle处理根块分裂的方式与处理普通的分支块的分裂有一点细微的差异,以确保无论根块上发生了多少次的分裂,总是可以在物理段的同一个位置找到根块.)
注意,这个递归的分裂操作这样沿着索引树不断攀升意味着,无论何时,索引总能保持平衡.

为什么这个神话如此牢固?

为什么这个关于不平衡的索引的神话能够长盛不衰,是否存在一些原因呢?我这答案是确实存在一些原因.
要切记,当我们讨论B-tree的时候,单词”balanced”的定义有非常严格的含义.然而,这个单词还有一种完全不同的解释.
例如,你将如何描述图-6中的这个索引,其中根块指向六个叶子块,但是其中一个叶子块是空的,有三个块几乎是空的,还有两个块塞的很满.(注意,从根块到叶子块的这些额外的说明是为了强调索引填充分布的多么不均匀;实际上,根块到每个叶子块都只有一个指针.)

图-6 “不平衡”的一种非技术理解

看到这种图案的索引,一个”人”的真实反应都会人为它”不平衡”.很明显,索引的右手边要比左手边”重”.很不幸,当技术表达意味着完全不同的东西的时候,这种非正式的人为表达应该更加恰当.
或许正是这种技术表达与非正式的人为表达之间的冲突导致了这种混淆.
在这种非正式的意义上,在基于序列值的字段上索引很容易就会变得”不平衡”,特别是它们被用来表征/处理先进先出(FIFO)队列机制的时候.然而,即使它们(在非正式语境中)是不平衡的,它们(在技术上)仍然是平衡的B-tree.
(推动使用类似于”扭曲”或者”分布不均匀”作为术语来描述这种类型的索引,或许会是个好主意.)
有时,仅仅几篇草率地使用术语的文章或报告就可能构建一个神话,在这个例子中,就是一个导致众多DBA浪费无数小时的时间去做不必要的索引重建的神话.
记住,你下一次认为Oracle表现愚蠢或者低效的时候,很可能问题是出在一个古老的误解上面,而不是Oracle软件本身的问题.

告警提醒

如果你还想进一步地研究,treedump选项还有一系列的问题需要注意.对于大部分的Oracle版本,它看似对索引段中的每个块都生成一行输出,这样可能会非常昂贵并且速度缓慢,因为它需要按顺序访问索引中的每一个数据块.然而,在Oracle 9.0中,跟踪文件看似会对每一个块做一个整块转储,这样会使得转储文件非常巨大,转储速度也会非常缓慢.
第二个问题是所有版本都一致的.如果这个索引是在定义主键约束或者唯一键约束时生成的,Oracle就会设置ind$表的flags字段的第13位,而这将导致treedump程序崩溃并报出错误”invalid value.”分区索引的分区段不会产生这个问题,但是对于所有其他类型的主键索引与唯一索引(包含非分区索引组织表,IOT),这都很恼人.先创建索引,再基于这个索引创建约束通常是个好主意, 这样处理可以避免除索引组织表外的其他所有条件下的问题. 在紧急情况下,你可以修改ind$表来清除这一位,但是很明显,需要先取得Oracle支持的认可.

结论

当谈到平衡B-tree索引的时候,术语”平衡”指的是从顶部到底部,而不是从左到右.
Oracle确实实现了一个版本的”平衡B-tree索引”,因此在任何时候,索引中的所有叶子块到根块的距离都是完全相同的,如果最近对这个索引作过分析的话,可以从视图user_indexes的字段blevel找到它,如果刚刚对这个索引执行过validate index的话,可以从视图index_stats的height字段(等价于blevel+1)得到.
当听到你应该经常重建索引,因为”这些索引已经变得不平衡”时,要抵制这种理由.因为它不是一个靠得住的理由.

建议继续学习：

1. 由浅入深探究mysql索引结构原理、性能分析与优化    (阅读：14945)
2. 浅谈MySQL索引背后的数据结构及算法    (阅读：9861)
3. 由浅入深理解索引的实现(2)    (阅读：6315)
4. HBase二级索引与Join    (阅读：5764)
5. 如何建立合适的索引？    (阅读：5335)
6. InnODB和MyISAM索引统计集合    (阅读：5161)
7. Innodb 表和索引结构    (阅读：4775)
8. mysql查询中利用索引的机制    (阅读：4686)
9. MySQL索引背后的数据结构及算法原理    (阅读：4402)
10. mysql索引浅析    (阅读：4062)