librelist archives

« back to archive

简单hash索引的原理与不足

简单hash索引的原理与不足

From:
fengxq
Date:
2012-06-14 @ 07:30
对于原理:
这个索引算法是对redis的hash和sorted set的简单的组合应用,
对于model的字段做索引。分两种情况:
1.数字型字段。字节使用model的id为value,字段的值作为score 加入到zset中。
    对于==,> ,< ,>= ,<=, !=等索引要求,直接使用redis的
zrangebyscore(key,min,max)指令实现即可。

2。字符串型字段。
     由于zset的score只能为数值,所以不能使用1类似的方式。所以使用了hash 
的方式。
即:以字段的值为hash的field,model的id作value。由于hash的value是不可以重 
复的,
而字段的值确实可能重复,所以,当hash一个实例的时候,如果发现这个field已 
经有了一个值
了,就吧这个值和新的值都放入到一个set(或list)中,而hash的值改为这个集合 
的名称。当一个
field的值发生改变时,先用旧值hash,删除field(value为id)或set(或list)中对 
应的id(value为set(或 list)名称)
     在索引时,分为2中情况。
     ==,~= :对于==,直接hash找到id或id的集合。对于~= 则是==的结果的补集
     对与其他的> , < , contains等,直接取hash的fields进行遍历,找出对应 
的id。

不足:
     1.字符串型算法复杂,如果zset的score能够支持字符串,则能够和数字型类 
似。而且也能够有O(log(n))的复杂度
     2.字符串型,除了==,~=外,都需要遍历hash的fields集合,复杂度为 
O(n),(由于hkeys指令得到的结果不是排序的,所以必须遍历)
         而==时,O(1)的复杂度,很好
         ~=时,可已认为是O(1)的复杂度

改进:
     其实zset可以有2个值得改进的地方:
     1.score支持字符串,
     2.对hash的fields做有序集合




Re: [bamboo] 简单hash索引的原理与不足

From:
Tang Daogang
Date:
2012-06-14 @ 09:09
其实还是可以。对很多应用可以大大加速!

2012/6/14 fengxq <fengxq@legerobot.com>

> 对于原理:
> 这个索引算法是对redis的hash和sorted set的简单的组合应用,
> 对于model的字段做索引。分两种情况:
> 1.数字型字段。字节使用model的id为value,字段的值作为score 加入到zset中。
>    对于==,> ,< ,>= ,<=, !=等索引要求,直接使用redis的
> zrangebyscore(key,min,max)指令实现即可。
>
> 2。字符串型字段。
>     由于zset的score只能为数值,所以不能使用1类似的方式。所以使用了hash
> 的方式。
> 即:以字段的值为hash的field,model的id作value。由于hash的value是不可以重
> 复的,
> 而字段的值确实可能重复,所以,当hash一个实例的时候,如果发现这个field已
> 经有了一个值
> 了,就吧这个值和新的值都放入到一个set(或list)中,而hash的值改为这个集合
> 的名称。当一个
> field的值发生改变时,先用旧值hash,删除field(value为id)或set(或list)中对
> 应的id(value为set(或 list)名称)
>     在索引时,分为2中情况。
>     ==,~= :对于==,直接hash找到id或id的集合。对于~= 则是==的结果的补集
>     对与其他的> , < , contains等,直接取hash的fields进行遍历,找出对应
> 的id。
>
> 不足:
>     1.字符串型算法复杂,如果zset的score能够支持字符串,则能够和数字型类
> 似。而且也能够有O(log(n))的复杂度
>     2.字符串型,除了==,~=外,都需要遍历hash的fields集合,复杂度为
> O(n),(由于hkeys指令得到的结果不是排序的,所以必须遍历)
>         而==时,O(1)的复杂度,很好
>         ~=时,可已认为是O(1)的复杂度
>
> 改进:
>     其实zset可以有2个值得改进的地方:
>     1.score支持字符串,
>     2.对hash的fields做有序集合
>
>
>
>
>
>


-- 
Nothing is impossible.

Re: [bamboo] 简单hash索引的原理与不

From:
fengxq
Date:
2012-06-15 @ 01:11
redis2.6之后,用script重写这些索引算法,可以更近一步的提高

On 06/14/2012 05:09 PM, Tang Daogang wrote:
> 其实还是可以。对很多应用可以大大加速!
>
> 2012/6/14 fengxq <fengxq@legerobot.com <mailto:fengxq@legerobot.com>>
>
>     对 于原理:
>     这个索引算法是对redis的hash和sorted set的简单的组合应用,
>     对于model的字段做索引。分两种情况:
>     1.数字型字段。字节使用model的id为value,字段的值作为score 加入到
>     zset中。
>        对于==,> ,< ,>= ,<=, !=等索引要求,直接使用redis的
>     zrangebyscore(key,min,max)指令实现即可。
>
>     2。字符串型字段。
>         由于zset的score只能为数值,所以不能使用1类似的方式。所以使用了hash
>     的方式。
>     即:以字段的值为hash的field,model的id作value。由于hash的value是不
>     可以重
>     复的,
>     而字段的值确实可能重复,所以,当hash一个实例的时候,如果发现这个
>     field已
>     经有了一个值
>     了,就吧这个值和新的值都放入到一个set(或list)中,而hash的值改为这
>     个集合
>     的名称。当一个
>     field的值发生改变时,先用旧值hash,删除field(value为id)或set(或
>     list)中对
>     应的id(value为set(或 list)名称)
>         在索引时,分为2中情况。
>         ==,~= :对于==,直接hash找到id或id的集合。对于~= 则是==的结
>     果的补集
>         对与其他的> , < , contains等,直接取hash的fields进行遍历,找出对应
>     的id。
>
>     不足:
>         1.字符串型算法复杂,如果zset的score能够支持字符串,则能够和数
>     字型类
>     似。而且也能够有O(log(n))的复杂度
>         2.字符串型,除了==,~=外,都需要遍历hash的fields集合,复杂度为
>     O(n),(由于hkeys指令得到的结果不是排序的,所以必须遍历)
>             而==时,O(1)的复杂度,很好
>             ~=时,可已认为是O(1)的复杂度
>
>     改进:
>         其实zset可以有2个值得改进的地方:
>         1.score支持字符串,
>         2.对hash的fields做有序集合
>
>
>
>
>
>
>
>
> -- 
> Nothing is impossible.
>