分类 索引 下的文章

重建索引-没那么简单

在ask tom看到一个很精彩的讨论,关于索引的重建,解释了很多问题,值得学习。

索引的“平衡”

贴子中的这句话引起了我的兴趣,因为之前习惯将重建索引安排到数据库定期维护中。

The time lag between index rebuilds should be approximate FOREVER. They would destroy the equilibrium that the system worked so hard to get to.

对于这个结论的解释是:

在对索引列进行反复更新时,这条记录在索引树上的位置也在不断变化移动,在这期间索引会不断的增大:当可移动的空间不够时,数据库会扩展空间(拆分block)。这将造成索引上有许多空闲的blocks(正常情况下这些空闲的Leaf blocks会在freelist上,在需要的时候会被重用),但这并不会造成问题,扩展到一定程度后,即便再插入新的数据,索引树也不需要再继续扩展,因为索引树上空闲空间已经足够多,可以被新数据重复利用了。

引用中的”平衡”就是指这:使用中Freelist上blocks共成的组成的索引。两者比例应该是最适合系统业务运行的(因为是通过实际业务操作一点一点形成的,就像HashMap一样,所占用空间并不能完全被利用,而是通过LoadFactor来控制),或者说是因为系统业务特点而造成了索引离散性,正常情况下这应该是索引的最佳状态

而当重建索引后,所有经过以上过程产生blocks清掉。但随着系统业务模块运行,反复的更新再次导致不断记录在索引的移动,而索引又重新开始尝试扩展到”最佳状态”的过程。

阅读全文

Btree索引详解

Btree索引(或Balanced Tree),是一种很普遍的数据库索引结构,oracle默认的索引类型(本文也主要依据oracle来讲)。其特点是定位高效、利用率高、自我平衡,特别适用于高基数字段,定位单条或小范围数据非常高效。理论上,使用Btree在亿条数据与100条数据中定位记录的花销相同。

数据结构利用率高、定位高效

Btree索引的数据结构如下:

btree_structure

 

结构看起来Btree索引与Binary Tree相似,但在细节上有所不同,上图中用不同颜色的标示出了Btree索引的几个主要特点:

  • 树形结构:由根节(root)、分支(branches)、叶(leaves)三级节点组成,其中分支节点可以有多层。
  • 多分支结构:与binary tree不相同的是,btree索引中单root/branch可以有多个子节点(超过2个)。
  • 双向链表:整个叶子节点部分是一个双向链表(后面会描述这个设计的作用)
  • 单个数据块中包括多条索引记录

这里先把几个特点罗列出来,后面会说到各自的作用。

结构上Btree与Binary Tree的区别,在于binary中每节点代表一个数值,而balanced中root和Btree节点中记录了多条”值范围”条目(如:[60-70][70-80]),这些”值范围”条目分别指向在其范围内的叶子节点。既root与branch可以有多个分支,而不一定是两个,对数据块的利用率更高
阅读全文