Hash与Btree的区别
当记录号不是用于数据存取的主键时,应该使用 Hash和Btree算法
。 (如果记录号是用于数据存取的一个二级关键字,那么还是可以选择Btree算法,因为它支持一个主键和一个记录号同时存取。)
Btree中的主键是有序存储
,记录间的关联是依靠次序。并且其结构能随数据的插入和删除进行动态调整。为了代码的简单,DB没有实现对关键字的前缀码压缩。Btree支持对数据查询、插入、删除的常数级速度。关键字可以为任意的数据结构。 因此,当在主键有序时,Btree算法应该被使用
。例如,如果主键是时间戳, 那么8点时间戳后面跟随的就是9点时间戳, 这种情况下,Btree算法一般是正确的选择。再来个例子:如果主键是名字,应用需要取出所有同姓的记录,那么Btree 存取方法同样是个好选择。
Hash 和 Btree 两种方式在小的数据集合上几乎没有性能的差别
。不过,由于Hash使用的是扩展线性HASH算法(extended linear hashing),可以根据HASH表的增长进行适当的调整。所以当一个数据集合足够大且关键字为随机分布时,采用Hash算法比较好
。
Queue和Recno区别
当用记录号作为数据存取的主键时,应该使用 Queue和Recno存取方法
。记录号由算法本身生成。实际上,这和关系型数据库中逻辑主键通常定义为int AUTO型是同一个概念。两者基本上都是建立在Btree算法之上,提供存储有序数据的接口。Queue的优势在于:由于其记录为定长,在插入操作时把记录插入到队列的尾部,所以速度最快,而且它执行上锁和并发处理的水平也相当高。 Recno 的长处在于它支持一些Queue不能实现的特征,比如可变长记录和支持flat-text文件。
记录号可以是可变的或者不变的: 可变指的是当记录被删除或者插入记录号发生变化;不变指的是记录号无论数据库如何操作,记录号都不会发生改变。 基于记录号存取在Btree方式下也是可行的。但是,记录号是可变,当记录删除或插入时,数据库内的其他记录的记录号都将发生改变。 Queue存取方法总是用固定的方式运行,不管数据库如何操作,记录号始终改变。 Recno 可以被设置为不变和可变两种形式。
另外,Recno为数据库提供支持flat-text文件的永久存储和数据在读或修改时提供一个快速的临时存储空间。
一个表格:
存储方式 |
描述 |
选择场景 |
BTree |
关键字有序存储,并且其结构能随数据的插入和删除进行动态调整。
为了代码的简单,
Berkeley DB
没有实现对关键字的前缀码压缩。
B+
树支持对数据查询、插入、删除的常数级速度。关键字可以为任意的数据结构
|
1
、
当
Key
为复杂类型时。
2
、
当
Key
有序时。
|
Hash |
DB
中实际使用的是扩展线性
HASH
算法(
extended linear hashing
),
可以根据
HASH
表的增长进行适当的调整。关键字可以为任意的数据结构。
|
1
、
当
Key
为复杂类型。
2
、
当数据较大且
key
随机分布时。
|
Recno |
要求每一个记录都有一个逻辑纪录号,逻辑纪录号由算法本身生成。
相当于关系数据库中的自动增长字段。
Recho
建立在
B+
树算法之上,提供了一个存储有序数据的接口。
记录的长度可以为定长或不定长。
|
1
、
当
key
为逻辑记录号时。
2
、
当非高并发的情况下。
|
Queue |
和
Recno
方式接近
,
只不过记录的长度为定长。
数据以定长记录方式存储在队列中,插入操作把记录插入到队列的尾部,
相比之下插入速度是最快的。
|
1
、
当
key
为逻辑记录号时。
2
、
定长记录。
3
、
高并发的情况下。
|
分享到:
相关推荐
爬取文件用Berkeley DB存储 提高性能: 常用操作系统不善于处理大量小文件 基于URL Ranking的优先级队列 主题爬虫: 机器学习算法对链接与主题相关度进行评估,并按照得出的优先级顺序进行爬取 爬虫礼仪 遵循爬虫...
爬虫相关知识代码 读书笔记《自己动手写网络爬虫》,自己敲的代码。...BDBFrontier 使用Berkeley DB 来做爬虫的前端url爬取列表存储 Crawler 爬虫一只,采用了宽度优先的方式爬取网络,并且使用httpclien4.3来
爬取文件用Berkeley DB存储 提高性能: 常用操作系统不善于处理大量小文件 基于URL Ranking的优先级队列 主题爬虫: 机器学习算法对链接与主题相关度进行评估,并按照得出的优先级顺序进行爬取 爬虫礼仪 遵循爬虫...
但是目前常用的嵌入式数据库(如SQLite、Berkeley DB等)均需嵌入式操作系统的支持,且对嵌入式系统的内存、CPU处理速度等有较高要求,只能应用在比较高端的嵌入式系统中。在低端的嵌入式系统中,传统的数据管理方法...
* Key-Value 是面向高性能的并发读/写的缓存存储,例如 MemcacheDB、Berkeley DB、Redis、Flare * Document-Oriented 是面向海量数据访问的文档存储,例如 MongoDB、CouchDB 虚拟化技术 * Popek 和 Goldberg 指出...
但是目前常用的嵌入式数据库(如SQLite、Berkeley DB等)均需嵌入式操作系统的支持,且对嵌入式系统的内存、CPU处理速度等有较高要求,只能应用在比较高端的嵌入式系统中。在低端的嵌入式系统中,传统的数据管理方法...
* 键值(Key-Value)存储数据库:相关产品有 Tokyo Cabinet/Tyrant、Redis、Voldemort、Berkeley DB。典型应用:内容缓存,主要用于处理大量数据的高访问负载。数据模型:一系列键值对。优势:快速查询;劣势:存储的...
13.5 Berkeley DB 226 13.6 小结 228 第四部分 掌握NoSQL 第14章 选择NoSQL 230 14.1 比较NoSQL产品 230 14.1.1 可扩展性 230 14.1.2 事务完整性和一致性 233 14.1.3 数据模型 233 14.1.4 查询支持 235 ...
dbm模块用来读取标准的UNIX-dbm数据库文件,gdbm用来读取GNU dbm数据库文件,dbhash用来读取Berkeley DB数据库文件。所有的这些模块提供了一个对象实现了基于字符串的持久化的字典,他与字典dict非常相似,但是他的...
3.Berkeley DB:支持事务 一个事务是一个连续的一组数据库操作,就好像它是一个单一的工作单元进行。换言之,永远不会是完整的事务,除非该组内的每个单独的操作是成功的。如果在事务的任何操作失败,则整个事务将...
6) Berkeley DB模块 这只在SP中涉及, 主要是打开DB文件, 查询某个md5的位置. 主要涉及到DB* MediaDB, openDB, openMedia这两个函数 openDB: 参数为DB文件的名 openMedia: 参数为md5和一个整数指针, 返回FILE *以及该...
6) Berkeley DB模块 这只在SP中涉及, 主要是打开DB文件, 查询某个md5的位置. 主要涉及到DB* MediaDB, openDB, openMedia这两个函数 openDB: 参数为DB文件的名 openMedia: 参数为md5和一个整数指针, 返回FILE *以及该...
以下是该算法的略述: 清单 5. 主分配程序的伪代码 1. If our allocator has not been initialized, initialize it. 2. Add sizeof(struct mem_control_block) to the size requested. 3. start at managed_...