摘要:
本文对B
树索引的结构、内部管理等方面做了一个全面的介绍。同时深入探讨了一些与B
树索引有关的广为流传的说法,比如删除记录对索引的影响,定期重建索引能解决许多性能问题等。
1.B
树索引的相关概念
索引与表一样,也属于段(
segment
)的一种。里面存放了用户的数据,跟表一样需要占用磁盘空间。只
不
过,在索引里的数据存放形式与表里的数据存放形式非常的不一样。在理解索引时,可以想象一本书,其中书的内容就相当于表里的数据,而书前面的目录就相当于
该表的索引。同时,通常情况下,索引所占用的磁盘空间要比表要小的多,其主要作用是为了加快对数据的搜索速度,也可以用来保证数据的唯一性。
但是,索引作为一种可选的数据结构,你可以选择为某个表里的创建索引,也可以不创建。这是因为一旦创建了索引,就意味着
oracle
对表进行
DML
(包括
INSERT
、
UPDATE
、
DELETE
)时,必须处理额外的工作量(也就是对索引结构的维护)以及存储方面的开销。所以创建索引时,需要考虑创建索引所带来的查询性能方面的提高,与引起的额外的开销相比,是否值得。
从物理上说,索引通常可以分为:分区和非分区索引、常规
B
树索引、位图(
bitmap
)索引、翻转(
reverse
)索引等。其中,
B
树索引属于最常见的索引,由于我们的这篇文章主要就是对
B
树索引所做的探讨,因此下面只要说到索引,都是指
B
树索引。
B
树索引是一个典型的树结构,其包含的组件主要是:
1)
叶子节点(
Leaf node
):包含条目直接指向表里的数据行。
2)
分支节点(
Branch node
):包含的条目指向索引里其他的分支节点或者是叶子节点。
3)
根节点(
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
万行。该表中有一个列,列名为
goodid
,其类型为
char
(
8
),那么也就是说该
goodid
的长度为固定值:
8
。同时在该列上创建了一个
B
树索引。
在叶子节点中,每个索引条目都会在数据块中占一行空间。每一行用
2
到
3
个字节作为行头,行头用来存放标记以及锁定类型等信息。同时,在第一个表示索引的键值的字段中,每一个索引列都有
1
个字节表示数据长度,后面则是该列具体的值。那么对于本例来说,在叶子节点中的一行所包含的数据大致如下图二所示:
从上图可以看到,在本例的叶子节点中,一个索引条目占
18
个字节。同时我们知道
8KB
的数据块中真正可以用来存放索引条目的空间为
6488
字节,那么在本例中,一个数据块中大约可以放
360
(
6488/18
)个索引条目。而对于我们表中的
130
万条记录来说,则需要大约
3611
(
1300000/360
)个叶子节点块。
而对于分支节点里的一个条目(一行)来说,由于它只需保存所链接的其他索引块的地址即可,而不需要保存具体的数据行在哪里,因此它所占用的空间要比叶子节点要少。分支节点的一行中所存放的所链接的最小键值所需空间与上面所描述的叶子节点相同;而存放的索引块的地址只需要
4
个字节,比叶子节点中所存放的
ROWID
少了
2
个字节,少的这
2
个字节也就是
ROWID
中用来描述在数据块中的行号所需的空间。因此,本例中在分支节点中的一行所包含的数据大致如下图三所示:
从上图可以看到,在本例的分支节点中,一个索引条目占
16
个字节。根据上面叶子节点相同的方式,我们可以知道一个分支索引块可以存放大约
405
(
6488/16
)个索引条目。而对于我们所需要的
3611
个叶子节点来说,则总共需要大约
9
个分支索引块。
这样,我们就知道了我们的这个索引有
2
层,第一层为
1
个根节点,第二层为
9
个分支节点,而叶子节点数为
3611
个,所指向的表的行数为
1300000
行。但是要注意,在
oracle
的索引中,层级号是倒过来的,也就是说假设某个索引有
N
层,则根节点的层级号为
N
,而根节点下一层的分支节点的层级号为
N-1
,依此类推。对本例来说,
9
个分支节点所在的层级号为
1
,而根节点所在的层级号为
2
。
转自: http://space.itpub.net/9842/viewspace-312607
相关推荐
深入研究B树索引 B树算法 B+树算法 经典算法 强烈推荐~
NULL 博文链接:https://aindf0128.iteye.com/blog/657524
原文转载自...本文对B树索引的结构、内部管理等方面做了一个全面的介绍。同时深入探讨了一些与B树索引有关的广为流传的说法,比如删除记录对索引的影响,定期重建索引能解决许多性能问题等。
该算法通过在预处理阶段加入一个场景层次信息索引表,将剖分平面固定为中剖面,并利用栈存储下一结点所需信息,节约了一半的存储空间;此外,将剖分轴按照最大轴向进行剖分,从而减少了光线同时穿过两个子结点的可能...
包括:[Oracle]深入研究B-树索引、ORACLE函数大全、Python 核心编程 第二版、重构-改善既有代码的设计等资料
4.3.3 B树中的查找 4.3.4 范围查询 4.3.5 B树的插入 4.3.6 B树的删除 4.3.7 B树的效率 习题 4.4 散列表 4.4.1 辅存散列表 4.4.2 散列表的插入 4.4.3 散列表的删除 4.4.4 散列表索引的效率 ...
每一小节通常以对相关历史素材的讨论结束,讨论了在每一算法领域的原创研究。 本书的特点可以概括为以下几个方面: 1.概念清晰,广度、深度兼顾。 本书收集了现代计算机常用的数据结构和算法,并作了系统而深入...
《MySQL内核:InnoDB存储引擎 卷1》由资深MySQL专家,机工畅销图书作者亲自执笔,在以往出版的两本InnoDB介绍性图书的基础之上,更深入地介绍InnoDB存储引擎的内核,例如latch、B+树索引、事务、锁等,从源代码的...
每一小节通常以对相关历史素材的讨论结束,讨论了在每一算法领域的原创研究。 本书的特点可以概括为以下几个方面: 1.概念清晰,广度、深度兼顾。 本书收集了现代计算机常用的数据结构和算法,并作了系统而深入...
第一部分 基础 第1章 开篇 3 1.1 一次友好的对话 3 1.2 准确的问题描述 4 1.3 程序设计 4 1.4 实现概要 5 1.5 原理 6 1.6 习题 7 1.7 深入阅读 9 第2章 啊哈! 算法 11 2.1 三个问题 11 2.2 无处不在的二...
1 983年,Robert开始攻读计算机信息系统的学位,随后转而研究“PC故障”并开始使用数据库语言(从dBase到SQL Server)进行编程,于1990年获得商业管理学位。此外,他还获得了CMA、MCSD、MCT以及MCDBA等认证。Robert...
1 983年,Robert开始攻读计算机信息系统的学位,随后转而研究“PC故障”并开始使用数据库语言(从dBase到SQL Server)进行编程,于1990年获得商业管理学位。此外,他还获得了CMA、MCSD、MCT以及MCDBA等认证。Robert...
12.2.1 B-树索引 339 12.2.2 位图索引 340 12.2.3 索引组织表 341 12.3 分区索引 343 12.3.1 局部索引 343 12.3.2 全局索引 345 12.3.3 散列分区与范围分区 346 12.4 与应用特点相匹配的解决方案 348 ...
深入剖析ASP.NET组件设计]一书第三章关于ASP.NET运行原理讲述的补白 asp.net 运行机制初探(httpModule加载) 利用反射来查看对象中的私有变量 关于反射中创建类型实例的两种方法 ASP.Net应用程序的多进程模型 NET委托...
没问题——你完全可以自己深入研究并找到答案。这听起来有点恐怖和不现实,是吗?一点儿也不,我写这本书的目的就是向你讲解并示范平常就可以用于解决各种各样问题的逆向工程技术。 不过我总是急于求成。也许你以前...