shifo0409
作者shifo04092019-04-11 09:19
信息分析/架构师, 日本ITS会社

ORACLE B*树索引原理-适用于ORACLE 11 R2/12c

字数 2430阅读 2278评论 1赞 2

在ORACLE中索引与表一样,也属于段(segment)的一种。里面存放了用户的数据,跟表一样需要占用磁盘空间。只不过,在索引里的数据存放形式与表里的数据存放形式就不太一样了。在理解索引时,可以想象一本书,其中书的内容就相当于表里的数据,而书前面的目录就相当于该表的索引。同时,通常情况下,索引所占用的磁盘空间要比表要小的多,其主要作用是为了加快对数据的搜索速度。

ORACLE默认的索引是B*树索引(平衡树结构中的一种)也就是我们说的“传统”索引,其实现与二叉查找树类似,目标是减少是减少ORACLE查找数据的时间。如果在一个数字列上有一个索引,那么理论上结构应该是这样的:

u34d2r51t8pb

u34d2r51t8pb

ox3hmmexunnu

ox3hmmexunnu

这个树最底层是叶子节点,包含索引键以及一个rowid(指向索引行)。叶子节点上面的称为分支块,用于在结构中实现导航。例如:想在索引中找到值42,从树顶开始查找,进入左分支,查找这个块,发现需要找的数据在“42...50”的叶子节点中。

另外,叶子节点之间是双向链表结构。也就是查找区间数据很容易,比如这样的条件,where x between 20 and 300。oracle只要刚开始找到大于或等于20的记录所在的叶子节点,接着往下扫描,找到大于或者等于300的块。这期间可能会跨叶子节点扫描,由于叶子节点之间是双向链表,故很容易实现跨叶子节点扫描。

B树有一个特点:所有的叶子节点都在同一层,也就是无论你查找哪一条数据,需要执行的I/O数据是一样的。一般的B树都是2或者3层。无论这个表有多少行数据,这样查找一条数据只需要2,3个I/O操作。

索引键压缩

假如一个表中,需要三列才能确认一行。那么我们在这个表示建立索引需要建立在这三列上。那么索引块的结构有可能是这样的。

3w8ssmf0j87p

3w8ssmf0j87p

我们会发现,第一列和第二列有很多值是重复的。其实这个时候可以进行压缩,对于重复的值,只保存一份。比如:

Sql代码 如下

drop index test_idx;

create index test_idx on

tab (owner,object_type,object_name)

compress &2;

compress&2表示压缩两列,这样能节省空间,但是会增加寻找的难度。也就是说,如果现在已经占用了大量的cpu时间,那么创建索引以压缩的方式,会使情况更糟糕。如果目前只是I/O操作比较多,那么压缩索引能加快处理速度,因为压缩之后的索引空间更少,那么块缓冲区应该能存放更多的索引块,块的命中率会提高。

反向键索引

假如我们建立的所有是在一个递增的列上,从上面的图1索引结构图,可以看出,相邻的值保存在同一索引块上。那么我们批量递增插入数据的时候,就会引起索引块的竞争。但是如果我们把索引值反转之后,原先相邻的值,就会相差很远,这样就降低了索引块的竞争。

反向索引有一个缺点,无法进行区间扫描。因为索引值已经反转,索引值相邻的值都是反转之后相邻的值,实际值其实相差很远,区间扫描无法进行。

那么,假设我们需要一个表,有一个主键是递增的,而且今后也不会在这个主键上进行区间扫描。但是有大批量的插入,这个时候就适合建立一个反向键索引。

B*树使用情况

什么时候应该使用B*树索引,什么时候又不行呢?主要看两点:

  1. 当需要通过索引访问表中很少一部分数据的时候,可以建立B*树索引。

    1. 即使需要访问表中多行,但是能只访问索引解决,也可以建立B*树索引。比如select count(1) from ...。

为什么只有访问少量数据的时候,才能使用B*树索引呢,举一例子:

假设我们通过索引读取一个表,而且要读取表中20%的行。若这个表中有100,000行,其中的20%就是20,000行。如果行大小约为80字节,在一个块大小为8KB的数据库中,每个块上则有大约100行。这说明,这个表有大约1000个块。了解了执行情况,计算起来就非常容易了。我们要通过索引读取20,000行;这说明,大约是20,000个TABLE ACCESS BY ROWID操作。为此要处理20,000个表块来执行这个查询。不过,整个表才有大约1000个块!最后会把表中的每一个块读取好处理20次。即使把行的大小提高一个数量级,达到每行800字节,这样每块有11.行,现在表中就有11.,000个块。要通过索引访问20,000行,仍要求我们把每一个块平均读取2次。还没有全表扫描块,全表扫描每一块只需访问一次。

物理组织

数据在磁盘上如何物理地组织,对上述例子有显著影响。如果那个索引的主键是按递增的方式存储在磁盘,那么上述例子的情况完全会不同,读取2W行数据完全不需要读取2W次块。读取一次块,即把这一块的数据读取到了缓存,这一块上符合条件的数据有很多,可能基本上都是想要的,那么相当于读一次块就读到了100行数据,我们需要2W行数据,那么读取200次块左右,而不是上述例子中的2W次块。上述例子是极限情况,上行数据和下一行数据都不在同一块上。

刚刚说的,读一次块就读了100行到缓存,其实有一个前提条件,前提是设置一个参数为100,。到oracle块读取数据的时候,有一个参数,代表一次读取多少行,叫做ARRAYSIZE。在java/jdbc中,connect或者statement对象有一个prefetch方法,代表一次读取多少行。假设设置成100,读取第一行的时候找到第一行所在的数据块读取,接着就开始读取第二行,这个时候发现第二行也在这个块上,于是直接就取了。接着就读取剩下的98行,直到读完100行数据。假设100行都在这个块上,那么只有一次I/O操作。也就是上面所说的一次读取了100行到缓存。但是假设那个参数设置的是10,那么相当于要读取10次,也就是同一个块要读取10次,才能获得100行数据。可见这个参数的设置是相当重要的。

我们会在下面的文章中接着学习关于索引的内容

如果觉得我的文章对您有用,请点赞。您的支持将鼓励我继续创作!

2

添加新评论1 条评论

wuwenpinwuwenpin软件开发工程师, 南京
2019-04-13 15:43
谢谢分享!
Ctrl+Enter 发表

作者其他文章

相关文章

相关问题

相关资料

X社区推广