摘要:
本文对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-tree)是一种自平衡的树数据结构,广泛应用于数据库和文件系统中,特别是在实现索引存储时。它能够保持数据有序,允许快速查找、插入和删除操作。本篇文章将深入探讨B树的核心概念、...
### 深入研究B树索引 #### B树索引概述 B树索引是一种高效的数据结构,广泛应用于数据库管理系统中,以提高数据检索的速度并确保数据的唯一性。B树索引的设计目的是为了最小化查找时间,尤其是在大规模数据集上。...
通过深入研究B树索引的原理与特性,数据库管理员和架构师可以更好地优化数据库性能和查询效率。正确地使用和管理B树索引,意味着可以在降低资源消耗和提升性能之间取得良好的平衡。理解B树索引的工作原理,对于设计...
总的来说,B树索引和自创Connect都是为了提升数据检索的效率。理解它们的原理和特点,有助于我们设计更高效的数据库系统,并在实际项目中选择最适合的数据结构。通过源码分享,我们可以深入研究这些数据结构的实现,...
cpp-DeepDataBase是一个使用B树索引实现的关系数据库引擎,它的设计目标是提供一个轻量级、高效的数据库解决方案。DeepDataBase是用C++编程语言编写的,这意味着它利用了面向对象的特性,同时保持了较低级别的性能...
3. B+树索引结构:B+树是一种广泛使用的树形结构数据索引方式,是B树的一种变种,特别适合用于磁盘存储。它能够有效地组织大量数据,并支持快速的查找、顺序访问、插入和删除操作。在数据库系统中,B+树被广泛用作...
磁盘数据页存储结构是数据库管理中的一项关键...在深入研究索引和查询原理之前,理解数据页的存储结构是必不可少的。只有这样,我们才能更好地掌握数据库系统的内部工作机制,进而设计出更优的索引和执行更高效的查询。
B*树(B-star tree)是B树的一个变种,它在B树的基础上进行了优化,以适应大规模数据存储和高效查询的需求。 B*树索引的核心特点在于它的分层结构,每个节点可以包含多个子节点,并且每个节点可以存储多个键值和...
在IT领域,数据结构是计算机科学中的核心概念之一,它为高效地存储和处理数据提供了理论基础。...对这些文件进行深入研究,不仅可以了解B+树索引的实现,还可以进一步提升C语言编程和数据结构理解的能力。
在探讨数据库和文件系统中数据结构的高效管理时,B树和B+树的讨论是无法绕开...B树和B+树,作为数据存储系统中不可或缺的核心组件,其重要性不言而喻,而对它们的深入探索和研究也将不断推动数据处理技术的发展和进步。
R树是由Guttman在1984年提出的一种多维索引结构,它是对B树的扩展,用于存储和查询具有空间属性的数据。R树的主要目标是在多维空间中有效地组织和检索数据,通过构建一种平衡的树形结构来降低搜索成本。 在R树中,...
通过对这些文件的研究,我们可以深入理解C语言和B树在实际问题中的应用,提升编程和数据结构设计的能力。 总的来说,C语言数据结构中的B树在图书管理系统中的应用,既展示了数据结构理论的实际价值,也锻炼了编程和...
B-树实际上是B树的一个变种,通常在数据库索引中较少提及,更多是在学术研究领域讨论。 **特点:** - 具有相同的关键字数量,但比B树少一个子节点; - 在每个节点中,关键字的数量等于子节点的数量减一; - 每个...
为了更好地理解这些数据结构,可以先从B-树入手,熟悉其基本原理和操作流程,然后再研究B+树的差异。项目提供的源代码可以作为实践平台,通过阅读和调试代码,加深对B-树和B+树的理解。 总结来说,这个C++实现的B-...
总结,这个压缩包提供了一个学习和研究B+树的良好平台,对于理解数据结构和算法,以及提高C语言编程技能都非常有价值。通过分析和实践其中的代码,你可以掌握B+树的基本操作,并了解到如何在实际项目中优化数据访问...
在关系数据库管理系统中,B+树索引是提高查询性能的关键技术。索引的构建和维护是数据库管理的重要组成部分,它需要在保证数据一致性的同时,提供高效的查询和更新操作。通过Java实现B+树算法,不仅可以优化数据库...
本文提出的基于B+树的电力大数据混合索引结构,正是针对这一需求所进行的研究。 首先,B+树作为一种广泛使用的数据结构,对于大规模数据的检索和管理具有重要意义。B+树属于平衡树的一种,其在数据库索引中的应用,...
**B树(B-tree)**是一种自平衡的查找树数据结构,它能够保持数据排序,适合用于数据库和文件系统等领域。...对于给定的压缩文件“bplustree”,可能包含了B树或B+树的示例代码和相关工具,供学习者深入研究和实践。