Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1745754
  • 博文数量: 335
  • 博客积分: 4690
  • 博客等级: 上校
  • 技术积分: 4341
  • 用 户 组: 普通用户
  • 注册时间: 2010-05-08 21:38
个人简介

无聊之人--除了技术,还是技术,你懂得

文章分类

全部博文(335)

文章存档

2016年(29)

2015年(18)

2014年(7)

2013年(86)

2012年(90)

2011年(105)

分类: DB2/Informix

2012-05-27 22:48:16

 
这节主要描述索引的前世今生的‘前世’
二分查找方法我们都已经很是熟悉,现在我们需要讨论的针对经排序的列表中,含有多个多个重复值得情况
在非唯一索引中,很是重要。
假设我们有一个7行的表,有一个类似索引的内存数组arr[7],因此(keyval,rowikdk)的值是通过arr[k-1],keyvarl,arr[k-1].rowidk给定的。假定数组是通过keyvarl进行排序的,即啊arr[0].keyval<=arr[1].keyvarl<=...<=arr[7].keyvar
其中查找特定元素的算法如下;

点击(此处)折叠或打开

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

  6. wile( diff > 0)
  7. /* loop unitl k to return */
  8. {
  9.  if (probe <=&& x> arr[probe].keyval)
  10. /* if probe too low,raise the probe position,otherwise lower the probe position homein answer.k we have reached finanl probe =
  11.  have we found x?
  12. if so ,we return k
  13. /*
  14. if(probe <= 6 && arr[probe].keyval)
  15.     probe = probe+diff;
  16. else 
  17. probe =probe-diff;
  18. diff= diff/2;
  19. }
  20. if ( probe <&& == arr[probe].keyval)
  21. return probe;
  22. else if(probe+<= 6
  23. && x == arr[probe+1].keyval)
  24. return probe-1;
  25. else return -1;
  26. }
通过上面给出的算法,我们假定给出的值为{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. 1 无前一次检测差值
  3. 2 262144
  4. 3 131072
  5. 4 65536
  6. 5 32768
  7. 6 16384
  8. 7 8192
  9. 8 4096
  10. 9 2048
  11. 10 1024
  12. 11 512
  13. 12 256
  14. 13 128
直到第13次,前一次的probe和当前的probe才有可能在同一个页面上。因为每一个页面上最多只有256项,所以在前12次中,该算饭不停的在不同的页面之间进行切换,如果访问的页面不在内存中,那么我们至少需要12次I/O操作。
正是由于二分查找的I/O效率原因,才最终导致了我们实际中见到的索引采用的都似乎B+树索引。

阅读(2339) | 评论(0) | 转发(0) |
0

上一篇:mysql

下一篇:C ---it is hard to say love to you !

给主人留下些什么吧!~~