好库网 好库网首页 | 我的好库
VC开发指南

谷歌 B-Tree C++ 模板库

发布者:vchelp
发布日期:2013/2/11 23:42:32   更新日期:2013/2/11 23:42:32
文件大小:48K
下载次数:146   浏览次数:1784
评分:4.80

源码目录结构图

介绍

谷歌开源团队近日发布了C++ B-Tree,这是一个C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btree_map、btree_set、btree_multimap和btree_multiset等模板。 

 

B-tree(多路搜索树,并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。这个数据结构一般用于数据库的索引,综合效率较高。 

 

由于B-trees可以保持磁盘寻道到最低限度,通常作为二次存储数据结构。对于内存中数据结构来说,将缓存未命中率保持在最低限度,可以产生更高的性能。C++ B-tree在搜索树时,通过在每个节点执行多个键比较,更好地利用了缓存。缓存行为的改善,可以使访问大型容器时的性能有显著提升。 

 

谷歌开源团队同时也表示,C++ B-tree容器也不是没有缺点,与标准STL容器不同的是,修改C++ B-tree容器,会令所有未在该容器中的迭代器失效。出于这个原因,谷歌在该库中还增加了一个“安全”容器版本,安全容器中的迭代器会保存当前key的副本,并会在使用迭代器时自动复位。 


评论

账号 密码 还没帐号呢,现在注册一个?



免责声明:好库网所展示的信息由发布者自行提供,其真实性、准确性和合法性由信息发布人负责。好库网不提供任何保证,并不承担任何法律责任。