Python中的Berkeley DB（2）：数据结构

Berkeley DB的数据存储结构

BDB支持四种数据存储结构及相应算法，官方称为访问方法（Access Method），分别是哈希表（Hash Table）、B树（BTree）、队列（Queue）、记录号（Recno）。在创建数据库的时候，必须通过dbtype参数将存储结构指定为上述结构中的一种，一旦数据库文件已创建则不能再更改其结构。

结构	描述
BTree	数据存储在一个有序的，平衡的树型结构中。在B树结构中，Key和Value都可以复杂的数据，这意味着它们可以是整数、字符串或复杂的数据结构。同时，这种结构允许重复的Key值，即两个记录拥有同样的Key（需要在创建数据库时打开XXX开关）。
哈希	数据存储在一个扩展的线性哈希表。同B树类似，Key和Value可以是复杂的数据，它也支持相同Key的记录（需要打开XXX）
队列	数据存储在一个固定记录长度的队列中。每个记录使用一个逻辑记录号作为它的Key。这种结构有利于快速在尾部插入，而且针对这种结构有一个专用的操作可以让你从队列头部删除并返回数据。这种结构的特点在于它提供记录级的锁，这非常有利于在并发访问队列时提供更高的性能。
记录号	基本同队列类似，它也使用一个逻辑记录号作为Key，但这里的记录可以是定长的，也可以是不定长的

B树（BTree）

通过指定dbtype=db.DB_BTREE用哈希表作为存储结构。B树中的B是Balanced的缩写，这意味着B树同其它树型结构的区别在于它的叶子节点是平均分布的，即不会出现某个分支很短，另外的分支很长的情况，这种结构非常有利于数据的快速定位。
![一个典型的BTree结构][1]
BDB中实现了B树的数据存储结构和相应算法，从下面的语句中可以看出，实际使用过程中，B树同哈希表基本一样。

>>> from bsddb import db  
>>> mydb = db.DB()  
>>> mydb.open('btree.db',dbtype = db.DB_BTREE, flags = db.DB_CREATE)
>>> mydb.put("number1","1")
>>> mydb.put("number2","2")
>>> print mydb.items()
[('number1', '1'),('number2', '2')]
>>> mydb.put("number1","123")       #注：可以直接用put方法修改数据
>>> print mydb.items()
[('number1', '123'),('number2', '2')]
>>> mydb.delete('number1')
>>> print mydb.items()
[('number2', '2')]
>>> print mydb.get('number2')
2

哈希表（Hash）

通过指定dbtype=db.DB_HASH使用哈希表作为存储结构。在上一节中，我们已经接触到这种数据结构。哈希表是一种能够过把键值（Key）映射到表中一个地址来访问记录，即给定一个Key，它通过一个f(Key)函数得到Value的存储地址，它几乎没有遍历或索引的操作，因此能够极快地定位到Key所对应的Value值。下面用一些简单的例子介绍哈希表数据结构的用法。
接着在上一节的Python环境中运行下面的命令：

>>> from bsddb import db  
>>> mydb = db.DB()  
>>> mydb.open('my.db')
>>> print mydb.items()          #打印全部记录
[('title', 'Berkeley DB in Python'), ('author', 'evancss')]
>>> print mydb.get('author')    #获取键名为'author'的值
evancss
>>> mydb.delete('author')       #删除键名为'author'的记录
>>> print mydb.items()
[('title', 'Berkeley DB in Python')]
>>> mydb.close()

队列（Queue）

通过指定dbtype=db.DB_QUEUE使用队列作为存储结构。初次使用这种结构你能感觉到它与B树和哈希有较大的差异。

>>> from bsddb import db
>>> quedb = db.DB()
>>> quedb.open('quedb.db',dbtype=db.DB_QUEUE,flags=db.DB_CREATE)
>>> quedb.put("number1","1")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: String keys not allowed for Recno and Queue DB's
>>>

上面的代码我们新建了一个名字为quedb的队列数据库，在使用我们熟悉的put方法时出错，原因是队列类型是不接受字符串类型的Key名称，Key只能是数字。

>>> quedb.put(1,"first item")
>>> print quedb.items()
[(1, 'first item ')]

实际应用中，经常Key对我们来说并不重要，我们可以使用一个简化的append方法向队列添加元素,这个方法会将添加元素的Key（记录号）作为返回值：

>>> quedb.append("second item")
2
>>> print quedb.items()
[(1, 'first item '), 
 (2, 'second item ')]

在队列中仍可以使用get方法获取值、使用put方法更改值，以及使用delete删除值：

>>> print quedb.get(1)
first item
>>> quedb.put(1,"1st item")
>>> print quedb.items()
[(1, '1st item '),
 (2, 'second item ')]
>>> quedb.delete(1)
>>> print quedb.items()
[(2, 'second item ')]

你可能想让这种数据结构操作起来也更像一个队列。可以使用另一个简化的功能consume，这样我们使用append在队列尾部加入数据，使用consume取出队列首部的数据，很方便地实现了FIFO的操作：

>>> quedb.append("third item")
3
>>> quedb.consume()
('\x02\x00\x00\x00', 'second item ')
>>> quedb.consume()
('\x03\x00\x00\x00', 'third item ')
>>> quedb.consume()
>>>

记录号

记录号数据结构有些特性和队列很类似，它支持put，get，append，delete等方法，同样，它的Key也只能是数字类型。需要注意的是，在创建数据库之前不需要指定记录长度，它也不能象队列类型那样使用consume方法。

>>> recdb=db.DB()
>>> recdb.open('recdb.db',dbtype=db.DB_RECNO,flags=db.DB_CREATE)
>>> recdb.put(1,"item 1")
>>> recdb.append("item 2")
2
>>> recdb.items()
[(1, 'item 1'), (2, 'item 2')]
>>> recdb.put(2,"item 2nd")
>>> recdb.items()
[(1, 'item 1'), (2, 'item 2nd')]
>>> recdb.delete(2)
>>> recdb.items()
[(1, 'item 1')]
>>>

选择正确的数据结构

首先你要知道准备使用BDB解决什么样的问题，如果你需要存储复杂的数据（包括字符串），那么你应当使用B树或者哈希。如果你想使用逻辑编号，那么应当使用队列或记录号。
那么问题来了，在B树、哈希，队列、记录号之间应当如何做选择呢？

选择B树还是哈希

当记录号不是用于数据存取的主键时，应该使用 Hash和Btree算法。 (如果记录号是用于数据存取的一个二级关键字，那么还是可以选择Btree算法，因为它支持一个主键和一个记录号同时存取。)

Btree中的主键是有序存储，记录间的关联是依靠次序。并且其结构能随数据的插入和删除进行动态调整。为了代码的简单，DB没有实现对关键字的前缀码压缩。Btree支持对数据查询、插入、删除的常数级速度。关键字可以为任意的数据结构。 因此，当在主键有序时，Btree算法应该被使用。例如，如果主键是时间戳， 那么8点时间戳后面跟随的就是9点时间戳， 这种情况下，Btree算法一般是正确的选择。再来个例子：如果主键是名字，应用需要取出所有同姓的记录，那么Btree 存取方法同样是个好选择。

Hash 和 Btree 两种方式在小的数据集合上几乎没有性能的差别。不过，由于Hash使用的是扩展线性HASH算法（extended linear hashing），可以根据HASH表的增长进行适当的调整。所以当一个数据集合足够大且关键字为随机分布时，采用Hash算法比较好。

选择队列还是记录号

当用记录号作为数据存取的主键时，应该使用 Queue和Recno存取方法。记录号由算法本身生成。实际上，这和关系型数据库中逻辑主键通常定义为int AUTO型是同一个概念。两者基本上都是建立在Btree算法之上，提供存储有序数据的接口。Queue的优势在于：由于其记录为定长，在插入操作时把记录插入到队列的尾部，所以速度最快，而且它执行上锁和并发处理的水平也相当高。 Recno 的长处在于它支持一些Queue不能实现的特征，比如可变长记录和支持flat-text文件。

记录号可以是可变的或者不变的： 可变指的是当记录被删除或者插入记录号发生变化；不变指的是记录号无论数据库如何操作，记录号都不会发生改变。 基于记录号存取在Btree方式下也是可行的。但是，记录号是可变，当记录删除或插入时，数据库内的其他记录的记录号都将发生改变。 Queue存取方法总是用固定的方式运行，不管数据库如何操作，记录号始终改变。 Recno 可以被设置为不变和可变两种形式。

另外，Recno为数据库提供支持flat-text文件的永久存储和数据在读或修改时提供一个快速的临时存储空间。

高级特性与线程安全

介绍cursor等
介绍多线程程序中使用的env

Case1：使用Berkeley DB进行URL去重

Case2：使用Berkeley DB作为缓冲队列

PS:实在抱歉，由于最近工作较忙，此系列暂停更新，有兴趣的朋友可以发邮件或留言沟通。