先话唠一下,oracle索引,有两类运用较广:
1)b-tree:OLTP(面向交易)
2)bitmap:OLAP(面向分析)
步入正题,先搭建测试环境:
SQL> create table tt as select * from dba_objects;
表已创建。
SQL> select count(*) from tt;
COUNT(*)
----------
50441
SQL> insert into tt select * from tt;
已创建50441行。
SQL> /
已创建100882行。
SQL> /
已创建201764行。
SQL> /
已创建403528行。
SQL> /
已创建807056行。
SQL> create index tt_index on tt(object_id) tablespace users;
索引已创建。
把索引tt_index的结构给dump出来:
SQL> select object_id from dba_objects where object_name='TT_INDEX';
OBJECT_ID
----------
53042
SQL> alter session set events 'immediate trace name treedump level 53042';
会话已更改。
SQL> show parameter user_dump_dest
NAME TYPE
------------------------------------ ----------------------
VALUE
------------------------------
user_dump_dest string
G:\ORACLE\PRODUCT\10.2.0\ADMIN
\ORCL\UDUMP
SQL> select distinct sid from v$mystat;
SID
----------
147
SQL> select paddr from v$session where sid=147;
PADDR
--------
CA280DDC
SQL> select spid from v$process where addr='CA280DDC';
SPID
------------------------
5360
到udump,把进程号为5360的文件打开,部分内容如下:
*** 2012-08-07 01:21:34.944
*** ACTION NAME:() 2012-08-07 01:21:34.902
*** MODULE NAME:(SQL*Plus) 2012-08-07 01:21:34.902
*** SERVICE NAME:(SYS$USERS) 2012-08-07 01:21:34.902
*** SESSION ID:(147.92) 2012-08-07 01:21:34.902
----- begin tree dump
branch: 0x10001bc 16777660 (0: nrow: 7, level: 2)
branch: 0x100595f 16800095 (-1: nrow: 578, level: 1)
leaf: 0x10001bd 16777661 (-1: nrow: 513 rrow: 513)
leaf: 0x10001be 16777662 (0: nrow: 513 rrow: 513)
leaf: 0x10001bf 16777663 (1: nrow: 513 rrow: 513)
leaf: 0x10001c0 16777664 (2: nrow: 513 rrow: 513)
leaf: 0x10001c1 16777665 (3: nrow: 513 rrow: 513)
leaf: 0x10001c2 16777666 (4: nrow: 513 rrow: 513)
leaf: 0x10001c3 16777667 (5: nrow: 484 rrow: 484)
leaf: 0x10001c4 16777668 (6: nrow: 478 rrow: 478)
leaf: 0x10001c5 16777669 (7: nrow: 478 rrow: 478)
leaf: 0x10001c6 16777670 (8: nrow: 478 rrow: 478)
leaf: 0x10001c7 16777671 (9: nrow: 478 rrow: 478)
leaf: 0x10001c8 16777672 (10: nrow: 478 rrow: 478)
leaf: 0x10001ca 16777674 (11: nrow: 481 rrow: 481)
leaf: 0x10001cb 16777675 (12: nrow: 478 rrow: 478)
leaf: 0x10001cc 16777676 (13: nrow: 478 rrow: 478)
leaf: 0x10001cd 16777677 (14: nrow: 478 rrow: 478)
leaf: 0x10001ce 16777678 (15: nrow: 478 rrow: 478)
leaf: 0x10001cf 16777679 (16: nrow: 478 rrow: 478)
由此可证明:b-tree中的b是balance,是棵平衡树。否则,一个branch下面只有两个leaf,才是二叉树。
上面:0x10001bd (16进制)和16777661(10进制)这两个,其实,是一样的。
SQL> select to_number('10001bd','xxxxxxx') from dual;
TO_NUMBER('10001BD','XXXXXXX')
------------------------------
16777661
而且,16777661包含两部分:文件号、数据块号。意指:这个地址是哪个数据文件上的第几个块
SQL> select dbms_utility.data_block_address_file( 16777661) from dual
DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(16777661)
----------------------------------------------
4
SQL> select dbms_utility.data_block_address_block( 16777661) from dua
DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(16777661)
-----------------------------------------------
445
由上,可得:4号文件的第445个块
将tt_index的内容给dump出来一下:
SQL> alter system dump datafile 4 block 445;
系统已更改。
部分内容摘入如下:
row#0[8024] flag: ------, lock: 0, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 00 01 ac 00 2d
row#1[8012] flag: ------, lock: 0, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 00 05 36 00 40
row#2[8000] flag: ------, lock: 0, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 00 08 01 00 1b
row#3[7988] flag: ------, lock: 0, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 00 0a a2 00 2d
row#4[7976] flag: ------, lock: 0, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 00 0d 69 00 48
tt表最小的object_id为2,对应的便是row#0[8024],那么2在oracle中的16进制是如何存储的呢?
SQL> select dump(2,16) from dual;
DUMP(2,16)
----------------------------------
Typ=2 Len=2: c1,3
由此,可知:2的存储是c1 03.也就是,第0行的第一列存储的值是2.
意味着,在索引的叶子节点里,我们在哪一列上创建索引,其实,oracle就是把该列的值保存到索引的叶子节点里。
索引里第一行第2列16进制数:01 00 01 ac 00 2d和rowid有啥关系呢?
SQL> select object_id,rowid from tt
2 where object_id=2
3 order by object_id,rowid;
OBJECT_ID ROWID
---------- ------------------
2 AAAM8xAAEAAAAGsAAt
2 AAAM8xAAEAAAAU2ABA
2 AAAM8xAAEAAAAgBAAb
...
其实,索引里第一行第2列16进制数:01 00 01 ac 00 2d表示的是rowid里面后三部分,也就是:fno、bno、rno。
rowid:AAAM8x AAE AAAAGs AAt。通过进制的转换,AAE AAAAGs AAt和01 00 01 ac 00 2d是一样的。
为什么只有后三个部分呢?说白点,书的目录会把书名给包括进去吗?书名就是对象编号、目录就是索引。
到此,我们把索引的内部结构给构造出来:
object_id rowid(后三部分)
......
草图如下:
分享到:
相关推荐
AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版
动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构,其查找的时间...
非索引的结构能满足所有需要,但自平衡的 B-树索引结构更能优化在大数据集上检索的性能。每个 B-树节点拥有多个键和指针。特定 B-树支持的一个节点中键的最大数量是那颗树的顺序。每个节点都具有一个潜在的 order+1 ...
前端开源库-binary-search-tree二进制搜索树,不同的二进制搜索树实现,包括自平衡树(AVL)
指得是数据行的delete操作从逻辑上删除的索引节点 的数量,要记住oracle在删除数据行后,将 “ 死 “ 节点保留在索引中,这样做可以加快sql删除操作的速度,因此oracle删除数据行后可以不必重新平衡索引。...
B树是一种自平衡树数据结构,可对数据进行排序,并允许以对数时间进行搜索,顺序访问,插入和删除。 B树是二叉搜索树的概括,一个节点可以有两个以上的子节点。 与自平衡二进制搜索树不同,B树非常适合于读写相对较...
红黑树(Red-Black Tree)是二叉搜索树(Binary Search Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点 之后...
javascript中的二进制搜索树和AVL树(自平衡树)实现。 二进制搜索树 AVL树(自平衡树) 目录 .min() 。最大限度() .lowerBound(k) .upperBound(k) 。根() 。数数() .traverseInOrder(cb) ...
JavaScript应用实例-AvlTree(平衡树).js
AutoJs源码-AvlTree(平衡树)。本资源购买前提醒:本源码都是实际autojs项目模板,安装好autojs直接运行即可打开。1、支持低版本autojs。2、资源仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您自己承担...
对于每个节点,从节点到后代叶的所有路径都包含相同数量的黑色节点。 红黑树是许多搜索树方案中的一种,它们是“平衡”的, 以便保证在最坏的情况下,基本的动态设置操作需要O(lg n)时间。 请注意,空叶节点或父...
采用平衡二叉树索引关键字,可以体会数据结构用法,也可用于项目,完全开源
研究了RN-Tree算法的基本原理,在实验中发现了算法存在的缺陷,即容易形成高度不平衡树,会造成查找效率的降低.提出了一种改进算法,通过控制RN-Tree的平衡因子,形成平衡树,以提高查找效率.编程模拟了改进的RN-Tree...
该算法通过R-tree对轨迹点进行索引搜索其领域内的轨迹点,然后根据TRAOD算法对R-tree索引出来的轨迹点进行异常轨迹的检测,这样可以提高算法的运行速度。真实数据实验测试表明,该算法比最新的TRAOD异常轨迹挖掘算法...
当数据庞杂时,B 树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B 树结构,首先通过调整叶子节点与非叶子节点的数量关系,以降低树的深度;然后优化原插入算法,在分裂节点前进行平衡处理...
fruit --treep平衡树 Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左子树和右子树也分别是一个Treap,和一般的二叉搜索树不同的是,Treap纪录一个额外的数据,就是优先级。Treap在以关键码构成二叉搜索树的...
我自己写的SBTree的实现 参考了http://www.nocow.cn/index.php/Size_Balanced_Tree的算法 声明:此源码可以用于商业用途,但请注明来源于random
加权平衡树储存记账信息的方式是对应用真正有用的属性:一棵树下元素的数量等于它的根的大小,然而这个根的大小是一个用来实现顺序统计树操作的有用数据,也就是说,可以得到一个大小为n的集合下的最大元素或者决定...
AVL平衡树数据结构,任意节点的左右子树高度差不超过1
针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的...