注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

几种常见数据结构的查找效率  

2015-02-15 15:43:19|  分类: 算法思想 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、问题的引入
在一些系统中,通常需要维护一些已ID为键值的数据结构,最为简单的例子比如说通过我们的身份证号码查找到性别、民族之类的信息。更为常见的形式是系统中配置文件中配置的一些商品的属性信息等。由于有些配置中这些配置项的数目比较大,对于典型的系统,这里假设说系统中存在以万为单位的配置项,更具体说可以认为存在3W条配置项。而且这个配置项会被非常频繁的使用(索引)到,为了提高查找效率,此时需要使用什么样的数据结构比较合理。
二、std::map
这个是最为简单直观的实现,建立一个map,通过键值可以方便的找到对应的配置内容。以当前的g++ stl库来说,它的map结构使用的是红黑树数据结构,这种结构不是严格的平衡二叉树。以这里讨论的3W级别来讨论,即时按照严格的平衡二叉树,它的层数为15(2^15=32K),考虑到红黑树不是严格的平衡二叉树结构,它的某些节点查找层数可能会接近30层。
三、B-tree
既然这里查找的层数是瓶颈的所在,众所周知的B-tree结构以层数少而著称,使用该数据结构是否可以提高查找呢?虽然说它从根到叶子节点之间的路径较短,但是它的每个内部节点包含的节点数量较多。假设说把这个Btree的高度限制在3层,那么每个内部节点大概需要包含2^5=32个指针,为了找到下一层的路由,即使对这32个节点进行折半查找,平均查找次数为5次,再考虑到总共3层,所以总共的查找次数并不能减少。
这种结构通常用在数据库中,它的特点是具有更好的局部性,更好的局部性则意味着更好的磁盘IO操作。
四、hash结构
这种是看起来最没有技术含量的,但是在某些情况下它又的确可以达到非常快的查找效率,但是谁也不能保证一定一定能获得很好的效率。查找的效率依赖hash的算法是否均匀,并且和输入的数据也有关系,这种结构的稳定性不能保证,只是说它通常会比较快。
另一方面,通常的hash都会涉及到将hash的结果缩小到任意的范围之内,而这个缩小通常就是通过取模操作实现,取模进而意味着消耗更大的除法运算(虽然常量除法可以转换为乘法、甚至一些2的整数幂可以转换为移位,但这些都不通用),和使用红黑树的"比较—迭代"操作相比,这个操作代价也会比较大。
五、radix-tree
在内核中使用了两种这种类型的数据结构,一种是idr相关、另一个就是radix-tree相关。对于idr的使用场景印象并不深刻,但是对于radix-tree大家一定熟悉,因为每个文件的内部页面就是通过这种radix-tree结构来实现的。struct inode-->i_mapping(struct address_space)-->struct radix_tree_root page_tree; /* radix tree of all pages */。
以更为常见的radix-tree为例,它的思想就是减少前面看到的Btree内部节点的查找消耗。在btree的内部,当寻找下一层路由时,需要在内部节点中进行二分查找,而radix-tree则将这个二分查找省略掉,通过数组下表一次性查找到。
通常每个中间节点也是我们常见的
linux-2.6.21\init\Kconfig
config BASE_FULL
default y
config BASE_SMALL
int
default 0 if BASE_FULL
default 1 if !BASE_FULL
linux-2.6.21\lib\radix-tree.c
#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
#endif
也就是说,默认情况下每个内部节点包含了2^4=16个内部节点,在内部路由时,根据键值的特定bit段的值(RADIX_TREE_MAP_SHIFT个bit对应的数值)作为下标来访问下面结构的slots元素
struct radix_tree_node {
unsigned int height; /* Height from the bottom */
unsigned int count;
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

linux-2.6.21\lib\radix-tree.c
do {
slot = (struct radix_tree_node **)
(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
node = rcu_dereference(*slot);
if (node == NULL)
return NULL;

shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);
以RADIX_TREE_MAP_SIZE=4为例,当查找0x1234abcd这个键值时,它执行的内部节点分别是依次以d,c,b,a,4,3,2,1作为slots的下标。这里注意下它是从最低bit位开始到最高bit位作为索引的,这样做有两个好处,一方面在键值较小的情况下,这棵树的层数可以较低;另一方面,低位差别较大,上面的槽位分布更加随机,其实看下微机原理中cache的结构,它也是以最低位作为索引的。

  评论这张
 
阅读(999)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017