学分指南  学分抽奖  学分竞答  学分竞猜
普通帖关于"二级索引"的一个公式
421145227 2008-11-11 21:46:34 [个人资料] [Blog]
[回复] 楼主 分数:0

关于"二级索引"的一个公式

内容摘自:汤版OS.

假设有n=1000000(100万)个表项,现欲采用二级索引方式进行访问.
若100个表项为一组,则第一级索引有10000(1万)个表项;再设第二级索引的每组也是100个表项,那么它也有100个表项.
则平均查找次数为[(3/2)√￣n] .这样算出来需平均查找150次.
请问这个公式是怎么来的呢?如果换成别的分组方式那查找次数又会是多少呢?谢谢~~
  
slbx32 2008-11-12 0:03:39 [个人资料] [Blog]
[回复] [引用] 第1楼 得分:0
没见过,,路过,,..以后再来看看
  
syhnjs 2008-11-12 0:52:13 [个人资料] [Blog]
[回复] [引用] 第2楼 得分:0
总记录数为N，将系统有两级索引，则第一级别的索引表有N1/3个，第二级别的索引表有N1/3个，第二级索引表对应N1/3个记录。
检索某一个记录，需要先查询一级索引（检索记录的平均次数为（1/2）N1/3），然后查询二级索引（检索记录的平均次数为（1/2）N1/3），最后查询记录（检索记录的平均次数为（1/2）N1/3）。因此，即为（3/2）N1/3）。
  
广告也精彩
 
1
快速回复：
注意：本论坛里的任何言论仅代表发言者个人的观点，与学赛网立场无关。请对您的言论负责，遵守中华人民共和国有关法律、法规。如果您的帖子违反学赛网论坛规则，将立即删除；如果再次发布，则封IP。
loading...