- 浏览: 105917 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (75)
- JVM (22)
- 数据结构 (11)
- java 基础 (16)
- gc (6)
- jmock (1)
- Google (2)
- MapReduce (1)
- Memory (2)
- 算法 (2)
- cglib (1)
- jdk (3)
- 虚拟机 (3)
- 安全 (2)
- 多线程 (1)
- 工作 (1)
- 生活 (1)
- MongoDB (2)
- Hadoop (4)
- HDFS (2)
- cms (2)
- Spring (1)
- 网络协议 (1)
- GitHub (1)
- MYSQL 调优和使用必读(转) (1)
- 分布式 (2)
- Big Data (0)
- 技术Blog (1)
- Hbase (2)
- Zookeeper (1)
- paper (0)
最新评论
-
lzc_java:
Java线程安全兼谈DCL -
select*from爱:
it's nice
IT业薪水大揭秘
3. B 树索引的访问
我们已经知道了 B 树索引的体系结构,那么当 oracle 需要访问索引里的某个索引条目时, oracle 是如何找
到该索引条目所在的数据块的呢?
当 oracle 进程需要访问数据文件里的数据块时, oracle 会有两种类型的 I/O 操作方式:
1) 随机访问,每次读取一个数据块(通过等待事件“ db file sequential read ”体现出来)。
2) 顺序访问,每次读取多个数据块(通过等待事件“ db file scattered read ”体现出来)。
第一种方式则是访问索引里的数据块,而第二种方式的 I/O 操作属于全表扫描。这里顺带有一个问题,为
何随机访问会对应到 db file sequential read 等待事件,而顺序访问则会对应到 db file scattered read 等待事件呢?这似乎反过来了,随机访问才应该是分散( scattered )的,而顺序访问才应该是顺序( sequential )的。其实,等待事件主要根据实际获取物理 I/O 块的方式来命名的,而不是根据其在 I/O 子系统的逻辑方式来命名的。下面对于如何获取索引数据块的方式中会对此进行说明。
我们看到前面对 B 树索引的体系结构的描述,可以知道其为一个树状的立体结构。其对应到数据文件里的
排列当然还是一个平面的形式,也就是像下面这样。因此,当 oracle 需要访问某个索引块的时候,势必会在这个结构上跳跃的移动。
/ 根 / 分支 / 分支 / 叶子 /…/ 叶子 / 分支 / 叶子 / 叶子 /…/ 叶子 / 分支 / 叶子 / 叶子 /…/ 叶子 / 分支 /.....
当 oracle 需要获得一个索引块时,首先从根节点开始,根据所要查找的键值,从而知道其所在的下一层的分支节点,然后访问下一层的分支节点,再次同样根据键值访问再下一层的分支节点,如此这般,最终访问到最底层的叶子节点。可以看出,其获得物理 I/O 块时,是一个接着一个,按照顺序,串行进行的。在获得最终物理块的过程中,我们不能同时读取多个块,因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此,在索引上访问数据块时,会对应到 db file sequential read 等待事件,其根源在于我们是按照顺序从一个索引块跳到另一个索引块,从而找到最终的索引块的。
那么对于全表扫描来说,则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时, oracle 知道要访问所有的数据块,因此唯一的问题就是尽可能高效的访问这些数据块。因此,这时 oracle 可以采用同步的方式,分几批,同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的,因此其对应到 db file scattered read 等待事件。
4.1 B 树索引的对于插入( INSERT )的管理
对于 B 树索引的插入情况的描述,可以分为两种情况:一种是在一个已经充满了数据的表上创建索引时,
索引是怎么管理的;另一种则是当一行接着一行向表里插入或更新或删除数据时,索引是怎么管理的。
对于第一种情况来说,比较简单。当在一个充满了数据的表上创建索引( create index 命令)时, oracle 会先扫描表里的数据并对其进行排序,然后生成叶子节点。生成所有的叶子节点以后,根据叶子节点的数量生成若干层级的分支节点,最后生成根节点。这个过程是很清晰的。
但是对于第二种情况来说,会复杂很多。我们结合一个例子来说明。为了方便起见,我们在一个数据块为 2KB 的表空间上创建一个测试表,并为该表创建一个索引,该索引同样位于 2KB 的表空间上。
- SQL> create table index_test(id char (150)) tablespace tbs_2k;
- SQL> create index idx_test on index_test(id) tablespace tbs_2k;
当一开始在一个空的表上创建索引的时候,该索引没有根节点,只有一个叶子节点。我们以树状形式转储上面的索引 idx_test 。
- <span style= "font-size: x-small;" ><span lang= "EN-US" >SQL> select object_id from user_objects where object_name= 'IDX_TEST' ;</span>
- </span>
- OBJECT_ID
- ----------
- 7390
- SQL> alter session set events 'immediate trace name treedump level 7390' ;
从转储文件可以看到,该索引中只有一个叶子节点( leaf )。
随 着数据不断被插入表里,该叶子节点中的索引条目也不断增加,当该叶子节点充满了索引条目而不能再放下新的索引条目时,该索引就必须扩张,必须再获取一个可 用的叶子节点。这时,索引就包含了两个叶子节点,但是两个叶子节点不可能单独存在的,这时它们两必须有一个上级的分支节点,其实这也就是根节点了。于是, 现在,我们的索引应该具有 3 个索引块,一个根节点,两个叶子节点。
我们来做个试验看看这个过程。我们先试着插入插入 10 条记录。注意,对于 2KB 的索引块同时 PCTFREE 为缺省的 10 %来说,只能使用其中大约 1623 字节( 2048 × 90 %× 88 %)。对于表 index_test 来说,叶子节点中的每个索引条目所占的空间大约为 161 个字节( 3 个字节行头 +1 个字节列长 +150 个字节列本身 +1 个字节列长 +6 个字节 ROWID ),那么当我们插入将 10 条记录以后,将消耗掉大约 1610 个字节。
- SQL> begin
- 2 for i in 1..10 loop
- 3 insert into index_test values (rpad(to_char(i*2),150, 'a' ));
- 4 end loop;
- 5 end ;
- 6 /
- SQL> commit ;
- SQL> select file_id,block_id,blocks from dba_extents where segment_name= 'IDX_TEST' ;
- FILE_ID BLOCK_ID BLOCKS
- ---------- ---------- ----------
- 7 417 32
- SQL> alter system dump datafile 7 block 418; --因为第一个块为块头,不含数据,所以转储第二个块。
打开跟踪文件以后,如下所示,可以发现 418 块仍然是一个叶子节点,包含 10 个索引条目,该索引块还没有被拆分。注意其中的 kdxcoavs 为 226 ,说明可用空间还剩 226 个字节,说明还可以插入一条记录。之所以与前面计算出来的只能放 10 条记录有出入,是因为可用的 1623 字节只是一个估计值。
- ……
- kdxcoavs 226
- ……
- row#0[1087] flag: -----, lock: 0
- col 0; len 150; (150):
- 31 30 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61
- 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61
- 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61
- 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61
- 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61
- 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61
- col 1; len 6; (6): 01 c0 01 82 00 04
- row#1[926] flag: -----, lock: 0
- ……
接下来,我们再次插入一条记录,以便基本充满该叶子节点,使得剩下的可用空间不足以再插入一条新的条目。如下所示。
这个时候我们再次转储 418 块以后会发现与前面转储的内容基本一致,只是又增加了一个索引条目。而这个时候,如果向表里再次插入一条新的记录的话,该叶子节点( 418 块)必须进行拆分。
- SQL> insert into index_test values (rpad(to_char(12*2),150, 'a' ));
- SQL> alter system dump datafile 7 block 418;
转储出 418 块以后,我们会发现,该索引块从叶子节点变成了根节点( kdxcolev 为 1 ,同时 row#0 部分的 col 1 为 TERM 表示根节点下没有其他分支节点)。这也就说明,当第一个叶子节点充满以后,进行分裂时,先获得两个可用的索引块作为新的叶子节点,然后将当前该叶子节点里所有的索引条目拷贝到这两个新获得的叶子节点,最后将原来的叶子节点改变为根节点。
- ……
- kdxcolev 1
- ……
- kdxbrlmc 29360547=0x1c001a3
- ……
- row#0[1909] dba: 29360548=0x1c001a4
- col 0; len 1; (1): 34
- col 1; TERM
- ----- end of branch block dump -----
同时,从上面的 kdxbrlmc 和 row#0 中的 dba 可以知道,该根节点分别指向 29360547 和 29360548 两个叶子节点。我们分别对这两个叶子节点进行转储看看里面放了些什么。
- SQL> select dbms_utility.data_block_address_file( 29360547 ),
- 2 dbms_utility.data_block_address_block( 29360547 ) from dual;
- DBMS_UTILITY.DATA_BLOCK_ADDRES DBMS_UTILITY.DATA_BLOCK_ADDRES
- ------------------------------ ------------------------------
- 7 419
- SQL> select dbms_utility.data_block_address_file(29360548 ),
- 2 dbms_utility.data_block_address_block( 29360548 ) from dual;
- DBMS_UTILITY.DATA_BLOCK_ADDRES DBMS_UTILITY.DATA_BLOCK_ADDRES
- ------------------------------ ------------------------------
- 7 420
- SQL> alter system dump datafile 7 block 419 ;
- SQL> alter system dump datafile 7 block 420 ;
在打开跟踪文件之前,我们先来看看表 index_test 里存放了哪些数据。
- SQL> select substr(id,1,2) from index_test order by substr(id,1,2);
- SUBSTR(ID,1,2)
- --------------
- 10
- 12
- 14
- 16
- 18
- 20
- 22
- 24
- 2a
- 4a
- 6a
- 8a
打开 419 块的跟踪文件可以发现,里面存放了 10 、 12 、 14 、 16 、 18 、 20 、 22 、 24 和 2a ;而 420 块的跟踪文件中记录了 4a 、 6a 和 8a 。也就是说,由于最后我们插入 24 的缘故,导致整个叶子节点发生分裂,从而将 10 、 12 、 14 、 16 、 18 、 20 、 22 、和 2a 放到 419 块里,而 4a 、 6a 和 8a 则放入 420 块里。然后,再将新的索引条目( 24 )插入对应的索引块里,也就是 419 块。
假如我们再最后不是插入 12*2 ,而是插入 9 会怎么样?我们重新测试一下,返回到 index_test 里有 11 条记录的情况下,然后我们再插入 9 。
这个时候, 418 块还是和原来一样变成了根节点,同时仍然生成出了 2 个叶子节点块,分别是 419 和 420 。但是有趣的是, 419 块里的内容与在插入 9 之前的叶子节点(当时的 418 块)的内容完全相同,而 420 块里则只有一个索引条目,也就是新插入的 9 。这也就是说,由于最后我们插入 9 的缘故,导致整个叶子节点发生分裂。但是分裂过程与插入 12*2 的情况是不一样的,这时该叶子节点的内容不进行拆分,而是直接完全拷贝到一个新的叶子节点( 419 )里,然后将新插入的 9 放入另外一个新的叶子节点( 420 )。我们应该注意到,插入的这个 9 表里所有记录里的最大字符串。
如果这时,我们再次插入 12*2 ,则会发现 419 号节点的分裂过程和前面描述的一样,会将原来放在 419 块里的 4a 、 6a 和 8a 放入一个新的叶子节点里( 421 块),然后将 12*2 放入 419 块,于是这个时候 419 块所含有的索引条目为 10 、 12 、 14 、 16 、 18 、 20 、 22 、和 2a 。同时 420 块没有发生变化。
根据上面的测试结果,我们可以总结一下叶子节点的拆分过程。这个过程需要分成两种情况,一种是插入的键值不是最大值;另一种是插入的键值是最大值。
对于第一种情况来说,当一个非最大键值要进入索引,但是发现所应进入的索引块不足以容纳当前键值时:
1) 从索引可用列表上获得一个新的索引数据块。
2) 将当前充满了的索引中的索引条目分成两部分,一部分是具有较小键值的,另一部分是具有较大键值的。 Oracle 会将具有较大键值的部分移入新的索引数据块,而较小键值的部分保持不动。
3) 将当前键值插入合适的索引块中,可能是原来空间不足的索引块,也可能是新的索引块。
4) 更新原来空间不足的索引块的 kdxlenxt 信息,使其指向新的索引块。
5) 更新位于原来空间不足的索引块右边的索引块里的 kdxleprv ,使其指向新的索引块。
6) 向原来空间不足的索引块的上一级的分支索引块中添加一个索引条目,该索引条目中保存新的索引块里的最小键值,以及新的索引块的地址。
从上面有关叶子节点分裂的过程可以看出,其过程是非常复杂的。因此如果发生的是第二种情况,则为了
简化该分裂过程, oracle 省略了上面的第二步,而是直接进入第三步,将新的键值插入新的索引块中。
在上例中,当叶子节点越来越多,导致原来的根节点不足以存放新的索引条目(这些索引条目指向叶子节点)时,则该根节点必须进行分裂。当根节点进行分裂时:
1) 从索引可用列表上获得两个新的索引数据块。
2) 将根节点中的索引条目分成两部分,这两部分分别放入两个新的索引块,从而形成两个新的分支节点。
3) 更新原来的根节点的索引条目,使其分别指向这两个新的索引块。
因此,这时的索引层次就变成了 2 层。同时可以看出,根节点索引块在物理上始终都是同一个索引块。而
随着数据量的不断增加,导致分支节点又要进行分裂。分支节点的分裂过程与根节点类似(实际上根节点分裂其实是分支节点分裂的一个特例而已):
1) 从索引可用列表上获得一个新的索引数据块。
2) 将当前满了的分支节点里的索引条目分成两部分,较小键值的部分不动,而较大键值的部分移入新的索引块。
3) 将新的索引条目插入合适的分支索引块。
4) 在上层分支索引块中添加一个新的索引条目,使其指向新加的分支索引块。
当数据量再次不断增加,导致原来的根节点不足以存放新的索引条目(这些索引条目指向分支节点)时,
再次引起根节点的分裂,其分裂过程与前面所说的由于叶子节点的增加而导致的根节点分裂的过程是一样的。
同时,根节点分裂以后,索引的层级再次递增。由此可以看出,根据 B 树索引的分裂机制,一个 B 树索引始终都是平衡的。注意,这里的平衡是指每个叶子节点与根节点的距离都是相同的。同时,从索引的分裂机制可以看出,当插入的键值始终都是增大的时候,索引总是向右扩展;而当插入的键值始终都是减小的时候,索引则总是向左扩展。
发表评论
-
哈希表
2013-05-03 11:03 1587转载自 ---- http://blog.java ... -
Java 链表
2013-01-18 15:27 935转载自 ---- http://359094247.iteye ... -
哈夫曼与压缩
2013-01-18 15:24 870转载自 ---- http://359094247.iteye ... -
排序算法java版(转载)
2011-08-10 14:06 853转载自 ---- http://yiyickf.iteye.c ... -
(转)B树、B-树、B+树、B*树都是什么
2011-08-03 16:55 664B 树 即二叉搜 ... -
(转)深入研究B树索引(五)续
2011-08-03 16:53 8365.3 重建 B 树索引对于查询性能的影响 ... -
(转)深入研究B树索引(五)
2011-08-03 16:53 8625. 重建 ... -
(转)深入研究B树索引(四)续
2011-08-03 16:52 7714.2 B 树索引的 ... -
(转)深入研究B树索引(二)
2011-08-03 16:51 8972. B 树索引的 ... -
(转)深入研究B树索引(一)
2011-08-03 16:50 1030摘要: 本文对B 树索引的结构、内部管理等方面做了一个 ...
相关推荐
深入研究B树索引 B树算法 B+树算法 经典算法 强烈推荐~
NULL 博文链接:https://aindf0128.iteye.com/blog/657524
原文转载自...本文对B树索引的结构、内部管理等方面做了一个全面的介绍。同时深入探讨了一些与B树索引有关的广为流传的说法,比如删除记录对索引的影响,定期重建索引能解决许多性能问题等。
包括:[Oracle]深入研究B-树索引、ORACLE函数大全、Python 核心编程 第二版、重构-改善既有代码的设计等资料
在深入讨论该算法的基础上,提出了中剖面kd-树算法。该算法通过在预处理阶段加入一个场景层次信息索引表,将剖分平面固定为中剖面,并利用栈存储下一结点所需信息,节约了一半的存储空间;此外,将剖分轴按照最大...
书中对数据库系统实现原理进行了深入阐述,并具体讨论了数据库管理系统的三个主要成分—存储管理器、查询处理器和事务管理器的实现技术。书中还对信息集成的最新技术,例如数据仓库、OLAP、数据挖掘、Mediator、数据...
《MySQL内核:InnoDB存储引擎 卷1》由资深MySQL专家,机工畅销图书作者亲自执笔,在以往出版的两本InnoDB介绍性图书的基础之上,更深入地介绍InnoDB存储引擎的内核,例如latch、B+树索引、事务、锁等,从源代码的...
除了这三章新的内容外,还增加了四个新节。如果单从目录来判断第2版中改动的范围的话,得出的结论很可能是改动不大。 但实际上,第2版中的改动远不止目录中显示的那样。以下列出了第2版中所做的主要改动(没有经过...
除了这三章新的内容外,还增加了四个新节。如果单从目录来判断第2版中改动的范围的话,得出的结论很可能是改动不大。 但实际上,第2版中的改动远不止目录中显示的那样。以下列出了第2版中所做的主要改动(没有经过...
第一部分 基础 第1章 开篇 3 1.1 一次友好的对话 3 1.2 准确的问题描述 4 1.3 程序设计 4 1.4 实现概要 5 1.5 原理 6 1.6 习题 7 1.7 深入阅读 9 第2章 啊哈!...2.1 三个问题 11 ...索引 221
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...
1.3.3 新一代数据库技术的研究和发展 1.4 关系数据库 1.4.1 关系模型 1.4.2 Codd十二法则 1.4.3 范式 1.5 SQL语言基础 1.5.1 SQL的历史 1.5.2 SQL语言的组成 1.5.3 SQL语句的结构 1.5.4 ...
1.3.3 新一代数据库技术的研究和发展 7 1.4 关系数据库 8 1.4.1 关系模型 8 1.4.2 codd十二法则 9 1.4.3 范式 10 1.5 sql语言基础 11 1.5.1 sql的历史 11 1.5.2 sql语言的组成 12 1.5.3 sql语句的结构 13 ...
没问题——你完全可以自己深入研究并找到答案。这听起来有点恐怖和不现实,是吗?一点儿也不,我写这本书的目的就是向你讲解并示范平常就可以用于解决各种各样问题的逆向工程技术。 不过我总是急于求成。也许你以前...
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 ...