Index查找算法也叫做块查找算法,比顺序查找有更快的效率,对于Linux文件系统以及数据库Btree索引结构的查找都能看到其身影,下以VB为例探讨下index查找算法

1

 

2

 

可以看出Index算法的特点:

1.树形结构,类似BTree,对于Oracle索引来讲,key必须是有序的,对于Index查找没有这个限制

2.数据有序性,也就是block块index_table结构体集合前一个block块index_table(i)中任意值<index_table(i+1)

简单讲就是max(index_table(i).key) < rnd(index_table(i+1).key)

3.首先通过search key条件匹配i节点(branch节点)中循环,比较key 在那个index_table(i),类似我们常见的”Index Range Scan”

4.循环3直到找i节点index_table(i)或者没有找到退出,对于i节点结构体构成的数组a(j)[类似leaf blocks],进行对比,以a(j).start,a(j)end为

上下限进行顺序查找

5.循环4直到找到a(j)=key或者没有找到退出查找,定位key=a(j),取出a(j)的位置位于第i个节点(branch block)的第(j)条目,这个就是

key在index 搜索结构体中的绝对位置(i,j),类似Oacle的rowid

6.假如我们在查找前已经知道key 位置Index结构体绝对位置(i,j),那么就能够立即定位到该key,从而快速的返回结果,类似Index Rowid    Access Scan