深入研究B树索引.doc
免费下载
深入研究
B
树索引
(
一
)
2010-03-25 01:43
摘要：本文对
树索引的结构、内部管理等方面做了一个全面的介绍。同
时深入探讨了一些与
树索引有关的广为流传的说法，比如删除记录对索引的
影响，定期重建索引能解决许多性能问题等。
B
树索引的相关概念
索引与表一样，也属于段（
segment
）的一种。里面存放了用户的数据，跟表一样需
要占用磁盘空间。只
不过，在索引里的数据存放形式与表里的数据存放形式非常的不一样。在理解索引时，可
以想象一本书，其中书的内容就相当于表里的数据，而书前面的目录就相当于该表的索
引。同时，通常情况下，索引所占用的磁盘空间要比表要小的多，其主要作用是为了加快
对数据的搜索速度，也可以用来保证数据的唯一性。
但是，索引作为一种可选的数据结构，你可以选择为某个表里的创建索引，也可以不
创 建 。 这 是 因 为 一 旦 创 建 了 索 引 ， 就 意 味 着
oracle
对 表 进 行
DML
（ 包 括
INSERT
、
UPDATE
、
DELETE
）时，必须处理额外的工作量（也就是对索引结构的维护）以及
存储方面的开销。所以创建索引时，需要考虑创建索引所带来的查询性能方面的提高，与
引起的额外的开销相比，是否值得。
从 物 理 上 说， 索 引 通 常 可 以 分 为 ： 分 区 和 非 分 区 索 引 、 常 规
B
树 索 引 、 位 图
（
bitmap
）索引、翻转（
reverse
）索引等。其中，
B
树索引属于最常见的索引，由于我们
的这篇文章主要就是对
B
树索引所做的探讨，因此下面只要说到索引，都是指
B
树索引。
B
树索引是一个典型的树结构，其包含的组件主要是：
<!--[if !supportLists]-->1)
<!--[endif]-->
叶子节点（
Leaf node
）：包含条目直接指向表里
的数据行。
<!--[if !supportLists]-->2)
<!--[endif]-->
分支节点（
Branch node
）：包含的条目指向索引
里其他的分支节点或者是叶子节点。
<!--[if !supportLists]-->3)
<!--[endif]-->
根节点（
Root node
）：一个
B
树索引只有一个根
节点，它实际就是位于树的最顶端的分支节点。
可以用下图一来描述
B
树索引的结构。其中，
B
表示分支节点，而
L
表示叶子节点。
对于分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（缺省
是升序排列，也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记
录）都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的
最小键值；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索
引块。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。
比如从上图一可以看到，对于根节点块来说，包含三条记录，分别为（
0 B1
）、（
500
B2
）、（
1000 B3
），它们指向三个分支节点块。其中的
0
、
500
和
1000
分别表示这三个分
支节点块所链接的键值的最小值。而
B1
、
B2
和
B3
则表示所指向的三个分支节点块的地
址。
对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的
（缺省是升序排列，也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做
每条记录）也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；
而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的
ROWID
，该
ROWID
是记录行在表里的物理地址。如果索引是创建在非分区表上或者索引是
分区表上的本地索引的话，则该
ROWID
占用
6
个字节；如果索引是创建在分区表上的全局
索引的话，则该
ROWID
占用
10
个字节。
知道这些信息以后，我们可以举个例子来说明如何估算每个索引能够包含多少条目，
以及对于表来说，所产生的索引大约多大。对于每个索引块来说，缺省的
PCTFREE
为
10
％，也就是说最多只能使用其中的
90
％。同时
9i
以后，这
90
％中也不可能用尽，只能
使用其中的
87
％左右。也就是说，
8KB
的数据块中能够实际用来存放索引数据的空间大约
为
6488
（
8192×90
％
×88
％）个字节。
假设我们有一个非分区表，表名为
warecountd
，其数据行数为
130
万行。该表中有一
of 65
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论