关于hash索引的范围查找疑惑....

玛莉隔壁

假设a为表原始数据：

array a={
#编号     姓名

'05'  ,    '赵七';
'04'  ,    '周六';
'01'  ,    '张三';
'02'  ,    '李四';
'03'  ,    '王五';
......
}


对'编号'进行hash索引后得到a_i：
array a_i={
#Rid  编号      姓名

1=> '01'  ,    '张三';
2=> '02'  ,    '李四';
3=> '03'  ,    '王五';
4=> '04'  ,    '周六';
5=> '05'  ,    '赵七';
......
}



当我们查询: select * from a where    编号  between ('02','04')  时可以如下优化：

1、先在索引中查找 “编号='02'” 即：a_i[2]
2、继续从a_i[2] --> next ...  遍历直到 “编号='04'” 即：a_i[4]  结束.
3、返回a_i[2]、a_i[3]、a_i[4] ....

这个过程应该比 btree 快多了吧，为什么说hash索引不擅长范围查找呢？

玛莉隔壁

为搞清楚问题，偶不怕砖头，豁出去了

willko

hash键不是有序的。
也就是不能用你的方法去做

玛莉隔壁

为何不能对 hash 键进行排序  

DQP

原帖由 玛莉隔壁 于 2009-1-12 16:34 发表
为何不能对 hash 键进行排序  

hash 值的顺序不能保证和数据的顺序相同（和所选用的hash算法有关）
你在一楼给出的例子只是个特例 是你想出来的hash算法

另外 你的ID太强了。。。

玛莉隔壁

笼统地说Memory engine中的hash不是这么实现的么？

andrefun

hash索引就相当于字典的key。

DQP

就用你在一楼 给出的例子吧

array a={
#编号     姓名

'05'  ,    '赵七';
'04'  ,    '周六';
'01'  ,    '张三';
'02'  ,    '李四';
'03'  ,    '王五';
......
}

假设hash 算法是 hash_id = 编号 % 4 然后用链表解决冲突问题 当然这只是个例子。。。

对'编号'进行hash索引后得到a_i：
array a_i={
#Rid  编号      姓名

1=> '01'  ,    '张三'; ==〉'05'  ,    '赵七';
2=> '02'  ,    '李四';
3=> '03'  ,    '王五';
4=> '04'  ,    '周六';
......
}

这时候 再按范围查询就不那么省事了

yueliangdao0608

你这种情况用不到HASH索引。

依我的看法，HASH结构因为没有B-TREE那样的树结构。
B-TREE的话可以确定到底是在左子树还是右子树。而HASH就不能确定改往哪里搜索，它只能一个一个的找，最终结果就成了FULL TABLE SCAN。



希望得到更完善的补充。