内存数组的二分查找-----B+树索引的由来

 

这节主要描述索引的前世今生的‘前世’

二分查找方法我们都已经很是熟悉，现在我们需要讨论的针对经排序的列表中，含有多个多个重复值得情况

在非唯一索引中，很是重要。

假设我们有一个7行的表，有一个类似索引的内存数组arr[7],因此(keyval,rowikdk)的值是通过arr[k-1],keyvarl,arr[k-1].rowidk给定的。假定数组是通过keyvarl进行排序的，即啊arr[0].keyval<=arr[1].keyvarl<=...<=arr[7].keyvar

其中查找特定元素的算法如下；

int binserch(int x)
/* return k so that arr[k].keyval ==x,or else -1 if no match; arr assumed to be external,dimmension 7 is wired in */
{
int probe= 3; /* start subscript =3 */
 diff =2 ; /* difference to 2nd probe */

wile( diff > 0)
/* loop unitl k to return */
{
 if (probe <=6 && x> arr[probe].keyval)
/* if probe too low,raise the probe position,otherwise lower the probe position homein answer.k we have reached finanl probe =k
 have we found x?
if so ,we return k
/*
if(probe <= 6 && arr[probe].keyval)
    probe = probe+diff;
else
probe =probe-diff;
diff= diff/2;
}
if ( probe <6 && == arr[probe].keyval)
return probe;
else if(probe+1 <= 6
&& x == arr[probe+1].keyval)
return probe-1;
else return -1;
}

通过上面给出的算法，我们假定给出的值为{1,7,7,8,9,9,10}，

如果x=1,二分法查找的数组的下标分为3,1,0，最后算法返回0，，

如果x=7,二分法查找的数组的小标分为3,1,0，然后因为arr[0].keyval不等于7，所以我们检测arr[1].keyval,发现它等于7，算法返回1.

如果x=8,二分查找一次检测3,1,2，返回3

。。。。。。。。。。。。。。

如果在数组中有重复值，那么上面的算法将返回是的x == arr[k].keyvalde 的最小小标K，

这也就为前面介绍的索引的扫描的时候，DBRM 将会扫描从等于该值得rowidK，开始的所有可能的rowid

...........

虽然可以证明该算法很有效，但是对于基于磁盘的查找来说却不是最优的。

可以证明对于磁盘上已经排序的列表进行二分查找，可能需要更多的I/O

100W个索引项的二分查找算法

假设rowid 为4个字节

（在DB2中，rowid有4个字节与5个字节两种，分区表为个4字节）

分区表4个字节的原因，

分区表最多4096个分区，分区大小为4G，其中每一个page的大小为4kb

5bytes=12 +28byges

其中12个比特用来定位分区号 2*12=4096

2*20=1G

剩余的20个比特刚好可以定为剩余4G大小的空间

索引项大小假设也为4个字节

因为数组中一项占8个字节，一个2KB的页面最多可以存放256个有序项，忽略每页的额外开销。

二分查找的收敛距离：

检测次数 与前一次检测的差值
1 无前一次检测差值
2 262144
3 131072
4 65536
5 32768
6 16384
7 8192
8 4096
9 2048
10 1024
11 512
12 256
13 128

直到第13次，前一次的probe和当前的probe才有可能在同一个页面上。因为每一个页面上最多只有256项，所以在前12次中，该算饭不停的在不同的页面之间进行切换，如果访问的页面不在内存中，那么我们至少需要12次I/O操作。

正是由于二分查找的I/O效率原因，才最终导致了我们实际中见到的索引采用的都似乎B+树索引。