一檬果、目的
??DBM提供了針對(duì)DBM-style顷蟀、string-keyed數(shù)據(jù)庫(kù)類(lèi)似字典的接口赃阀。
??dbm面向DBM數(shù)據(jù)庫(kù)丑瞧，利用簡(jiǎn)單的字符串值作為key來(lái)訪問(wèn)包括字符串的記錄甫恩。它內(nèi)置的whichdb()方法會(huì)識(shí)別 數(shù)據(jù)庫(kù)逆济，并使用合適的模塊來(lái)打開(kāi)數(shù)據(jù)庫(kù)。它經(jīng)常也用在shelve模塊的后端，shelve使用pickle模塊序列化對(duì)象后存入一個(gè)DBM數(shù)據(jù)庫(kù)奖慌。
??DBM對(duì)外提供的接口
extern int dbminit (char *file);
extern datum fetch (datum key);
extern int store (datum key, datum content);
extern int delete (datum key);
extern datum firstkey (void);
extern datum nextkey (datum key);
extern int dbmclose (void);
二霎终、數(shù)據(jù)庫(kù)類(lèi)型
??Python中自帶了多個(gè)訪問(wèn)DBM風(fēng)格數(shù)據(jù)庫(kù)的模塊。默認(rèn)的實(shí)現(xiàn)取決于當(dāng)前系統(tǒng)上可用的庫(kù)和編譯Python時(shí)使用的選項(xiàng)升薯。與特定實(shí)現(xiàn)分離的接口允許Python程序與其他語(yǔ)言的程序交換數(shù)據(jù)莱褒，且不會(huì)自動(dòng)在可用格式之間切換，也可編寫(xiě)在多個(gè)平臺(tái)上運(yùn)行的便攜式數(shù)據(jù)文件涎劈。
- dbm.gnu
??dbm.gnu是GNU項(xiàng)目中dbm庫(kù)版本的接口广凸，它與這里描述的其他DBM實(shí)現(xiàn)同樣的工作，對(duì)open()方法提供了flags標(biāo)志進(jìn)行了一些修改蛛枚。除了標(biāo)準(zhǔn)的'r'谅海、'w'、'c'蹦浦、'n'外扭吁，dbm.gun.open()還提供了：- 'f':表示使用fast模式打開(kāi)數(shù)據(jù)庫(kù)。這種模式下寫(xiě)入數(shù)據(jù)庫(kù)是一個(gè)異步操作盲镶。
- 's':表示使用synchronized模式打開(kāi)數(shù)據(jù)庫(kù)侥袜。這種模式下，對(duì)數(shù)據(jù)庫(kù)所做的更改會(huì)立即寫(xiě)入文件溉贿，而不是在數(shù)據(jù)庫(kù)關(guān)閉或其他同步操作時(shí)進(jìn)行延遲寫(xiě)入枫吧。
- 'u':表示使用無(wú)鎖打開(kāi)數(shù)據(jù)庫(kù)。
gdbm對(duì)應(yīng)的接口如下：
extern GDBM_FILE gdbm_fd_open (int fd, const char *file_name, int block_size, int flags, void (*fatal_func) (const char *)); extern GDBM_FILE gdbm_open (const char *, int, int, int, void (*)(const char *)); extern int gdbm_close (GDBM_FILE); extern int gdbm_store (GDBM_FILE, datum, datum, int); extern datum gdbm_fetch (GDBM_FILE, datum); extern int gdbm_delete (GDBM_FILE, datum); extern datum gdbm_firstkey (GDBM_FILE); extern datum gdbm_nextkey (GDBM_FILE, datum); extern int gdbm_reorganize (GDBM_FILE); extern int gdbm_sync (GDBM_FILE); extern int gdbm_exists (GDBM_FILE, datum); extern int gdbm_setopt (GDBM_FILE, int, void *, int); extern int gdbm_fdesc (GDBM_FILE); - dbm.ndbm
??dbm.ndbm 模塊提供了一個(gè) Unix 上 ndbm 的接口實(shí)現(xiàn)宇色，依賴(lài)于模塊在編譯時(shí)的配置九杂。模塊的 library 屬性會(huì)識(shí)別出 configure 的名稱(chēng)然后查找出擴(kuò)展模塊是什么時(shí)候進(jìn)行編譯的。
??ndbm對(duì)應(yīng)的接口如下：extern DBM *dbm_open (char *file, int flags, int mode); extern void dbm_close (DBM *dbf); extern datum dbm_fetch (DBM *dbf, datum key); extern int dbm_store (DBM *dbf, datum key, datum content, int flags); extern int dbm_delete (DBM *dbf, datum key); extern datum dbm_firstkey (DBM *dbf); extern datum dbm_nextkey (DBM *dbf); extern int dbm_error (DBM *dbf); extern void dbm_clearerr (DBM *dbf); extern int dbm_dirfno (DBM *dbf); extern int dbm_pagfno (DBM *dbf); extern int dbm_rdonly (DBM *dbf); - dbm.dumb
??當(dāng)沒(méi)有其他實(shí)現(xiàn)可用時(shí)宣蠕，dbm.dumb模塊為 DBM API 提供了一個(gè)可移植的回退實(shí)現(xiàn)例隆。 使用dbm.dumb不需要外部依賴(lài)，但比大多數(shù)其他實(shí)現(xiàn)要慢抢蚀。
??dbm镀层、gdbm適合存儲(chǔ)靜態(tài)的、索引話(huà)的數(shù)據(jù)結(jié)構(gòu)思币，適用于處理那些被頻繁訪問(wèn)但卻很少被更新的數(shù)據(jù)鹿响，因?yàn)樗鼊?chuàng)建數(shù)據(jù)項(xiàng)時(shí)非常慢羡微，但檢索數(shù)據(jù)項(xiàng)時(shí)非彻榷觯快。
三妈倔、gdbm頭文件
本系列中主要以gdbm代碼為例博投，對(duì)dbm的原理和實(shí)現(xiàn)進(jìn)行分析和說(shuō)明。
- 頭文件
- autoconf.h
由configure腳本根據(jù)config.h.in模版生成盯蝴。autoconf.h為平臺(tái)相關(guān)的頭文件毅哗、函數(shù)听怕、庫(kù)等定義常量標(biāo)志。 - systems.h
包含平臺(tái)相關(guān)的頭文件和代碼虑绵。一些函數(shù)不同平臺(tái)名稱(chēng)不一致尿瞭。system.h把這些函數(shù)和代碼編寫(xiě)成統(tǒng)一的接口，以供程序使用翅睛，這樣就隱藏了底層不同平臺(tái)的差異声搁。 - gdbmerror.h
gdbm的錯(cuò)誤碼列表。主要由內(nèi)存分配捕发、文件讀寫(xiě)疏旨、文件鎖定、數(shù)據(jù)庫(kù)操作方面的錯(cuò)誤扎酷。 - gdbmconst.h
gdbm要用到的一些常量定義檐涝。包括gdbm_open、gdbm_store法挨、gdbm_setopt的一些常量參數(shù)谁榜、桶緩存的大小。 - gdbmdefs.h
包含了gdbm數(shù)據(jù)庫(kù)文件的結(jié)構(gòu)凡纳。這些定義具有兼容性惰爬，它們既用在gdbm中，也用在dbm惫企、ndbm中撕瞧。
- autoconf.h
四、dbm數(shù)據(jù)存儲(chǔ)原理
??一般數(shù)據(jù)庫(kù)的實(shí)現(xiàn)大體思路是用一個(gè)數(shù)據(jù)文件存放數(shù)據(jù)狞尔，這個(gè)數(shù)據(jù)文件其實(shí)就是普通的文件丛版，但是文件的結(jié)構(gòu)設(shè)計(jì)很復(fù)雜。另外偏序，也可以使用一個(gè)文件來(lái)保存索引页畦，如果數(shù)據(jù)量不是很大，則可以把索引存放在內(nèi)存中(如mysql的heap)研儒。gdbm數(shù)據(jù)庫(kù)的存儲(chǔ)方式采用的是可擴(kuò)展散列表豫缨。
??散列基本思想：通過(guò)由散列函數(shù)決定鍵值與散列地址的對(duì)應(yīng)關(guān)系來(lái)實(shí)現(xiàn)存儲(chǔ)組織和查找運(yùn)算，按照散列存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱(chēng)為散列表端朵。
??散列技術(shù)：散列技術(shù)的核心是散列函數(shù)好芭。散列函數(shù)是一種將鍵值映射為散列表中的存儲(chǔ)位置的函數(shù)。對(duì)任意給定的動(dòng)態(tài)查找表T冲呢，如果選定了某個(gè)理想的散列函數(shù)H以及響應(yīng)的散列表L舍败，則對(duì)T中的每個(gè)數(shù)據(jù)元素X，函數(shù)值H(X.key)就是X在散列表L中的出處位置。插入或建表時(shí)數(shù)據(jù)元素X將被放置在該文件位置上邻薯，并且查找X時(shí)也到該位置上查找裙戏。
五、gdbm數(shù)據(jù)庫(kù)文件結(jié)構(gòu)
- 文件信息結(jié)構(gòu)gdbm_file_info
struct gdbm_file_info
{
char *name; // 文件名
unsigned read_write :2; // 讀寫(xiě)模式標(biāo)志
unsigned fast_write :1; // 同步寫(xiě)文件標(biāo)志
unsigned central_free :1; //
unsigned coalesce_blocks :1; //
unsigned file_locking :1; // 文件鎖標(biāo)志
unsigned memory_mapping :1; // 是否使用mmap
unsigned cloexec :1; // 是否使用GDBM_CLOEXEC標(biāo)志打開(kāi)數(shù)據(jù)庫(kù)
unsigned need_recovery :1; // 最后一個(gè)Fatal Error時(shí)厕诡，數(shù)據(jù)庫(kù)是否需要恢復(fù)
gdbm_error last_error; // 最后一個(gè)錯(cuò)誤碼
int last_syserror; // 最后一個(gè)系統(tǒng)錯(cuò)誤碼
char *last_errstr; // 最后一個(gè)錯(cuò)誤字符串描述
enum { LOCKING_NONE = 0, LOCKING_FLOCK, LOCKING_LOCKF, LOCKING_FCNTL } lock_type;
void (*fatal_err) (const char *); // 錯(cuò)誤處理函數(shù)指針
int desc; // 文件描述
gdbm_file_header *header; // 文件頭指針
off_t *dir; // 散列表目錄指針
cache_elem *bucket_cache; // 桶緩存數(shù)組指針
size_t cache_size; //
size_t last_read;
hash_bucket *bucket; // 當(dāng)前緩存項(xiàng)讀的桶指針
int bucket_dir; // 當(dāng)前目錄項(xiàng)的索引
cache_elem *cache_entry; // 當(dāng)前桶緩存項(xiàng)
unsigned header_changed :1;
unsigned directory_changed :1;
unsigned bucket_changed :1;
unsigned second_changed :1;
/* Mmap info */
size_t mapped_size_max;/* Max. allowed value for mapped_size */
void *mapped_region; /* Mapped region */
size_t mapped_size; /* Size of the region */
off_t mapped_pos; /* Current offset in the region */
off_t mapped_off; /* Position in the file where the region begins */
};
- 文件頭gdbm_file_header
typedef struct
{
int header_magic; // 版本
int block_size; // 最佳傳遞大小
off_t dir; // 散列目錄表的偏移地址
int dir_size; // 目錄項(xiàng)的大小
int dir_bits; // 目錄地址占用的比特?cái)?shù)
int bucket_size; // 桶的字節(jié)大小
int bucket_elems; // 桶中元素個(gè)數(shù)
off_t next_block; // 下一個(gè)未分配的塊的偏移地址
avail_block avail; // 可用塊
} gdbm_file_header;
- 散列桶hash_bucket
typedef struct
{
int av_count; // 可用塊元素個(gè)數(shù)
avail_elem bucket_avail[BUCKET_AVAIL]; // 可用塊元素列表
int bucket_bits; // 標(biāo)識(shí)桶的二進(jìn)制系列
int count; // 桶的元素個(gè)數(shù)
bucket_element h_table[1]; // 桶的元素列表(真正的可擴(kuò)展三列表累榜，它會(huì)隨著文件的增長(zhǎng)而分裂×橄樱可用塊元素中包含了可用存儲(chǔ)塊地址和大小信柿，桶元素中包含了要管理的關(guān)鍵字/數(shù)據(jù)的地址和大小)
} hash_bucket;
- 桶元素bucket_element
typedef struct
{
int hash_value; // 哈希值
char key_start[SMALL]; // 關(guān)鍵字的前SMALL字節(jié)
off_t data_pointer; // 關(guān)鍵字記錄的偏移地址
int key_size; // 關(guān)鍵字的大小
int data_size; // 數(shù)據(jù)大小
} bucket_element;
- 可用塊avail_block
typedef struct
{
int size; // 可用塊元素大小
int count; // 可用塊元素個(gè)數(shù)
off_t next_block; // 下一個(gè)可用塊的偏移地址
avail_elem av_table[1]; // 可用塊元素列表
} avail_block;
- 可用塊元素avail_elem
typedef struct
{
int av_size; // 可用塊大小
off_t av_adr; // 可用塊的偏移地址(磁盤(pán)文件上各個(gè)可用存儲(chǔ)塊本身的位置不會(huì)有任何改變，而是通過(guò)操作知識(shí)可用塊的avail_elem元素來(lái)對(duì)可用塊進(jìn)行存取)
} avail_elem;
- 桶緩存數(shù)組bucket_cache
cache_elem *bucket_cache; // 由多個(gè)緩存項(xiàng)組成的一個(gè)數(shù)組醒第，在桶緩存初始化時(shí)渔嚷，文件信息結(jié)構(gòu)dbf中bucket_cache指針指向這個(gè)數(shù)組
size_t cache_size;
- 桶緩存中的緩存項(xiàng)cache_elem
// 緩存中的緩存項(xiàng)cache_elem不僅包含了實(shí)際的桶，還包含了數(shù)據(jù)緩存塊及一些標(biāo)志稠曼。在桶緩存初始化時(shí)形病，dbf中的指針cache_entry初始時(shí)指向桶緩存中的第一個(gè)緩存項(xiàng)
typedef struct
{
hash_bucket * ca_bucket; // 實(shí)際桶指針
off_t ca_adr; // 偏移地址
char ca_changed; // 更改標(biāo)志
data_cache_elem ca_data; // 數(shù)據(jù)緩存
} cache_elem;
- 緩存項(xiàng)中的數(shù)據(jù)緩存元素data_cache_elem
typedef struct
{
int hash_val; // 哈希值
int data_size; // 數(shù)據(jù)長(zhǎng)度
int key_size; // 關(guān)鍵字長(zhǎng)度
char *dptr; // 指向數(shù)據(jù)起點(diǎn)的指針
size_t dsize; // 偏移位置值
int elem_loc; //
} data_cache_elem;
- 散列桶目錄表dir
off_t *dir; // 每個(gè)元素是一個(gè)off_t類(lèi)型，根據(jù)元素中存放的偏移地址值訪問(wèn)磁盤(pán)上相應(yīng)的散列桶
??存放在磁盤(pán)上的一個(gè)新的數(shù)據(jù)庫(kù)文件只包含頭文件gdbm_file_header霞幅、桶目錄表dir[dir_size/4]漠吻、初始的一個(gè)桶hash_bucket(以后隨著文件的增長(zhǎng)會(huì)分裂為多個(gè)桶)，它們按照順序存放司恳。這里gdbm_file_header中存放了活動(dòng)的可用塊avali_block以及下一個(gè)可分配可用塊的偏移地址途乃，avali_block中的avali_elem猜真正指出了數(shù)據(jù)存儲(chǔ)塊的大小和偏移地址。hash_bucket中的bucket_element有指向關(guān)鍵字/數(shù)據(jù)的指針data_pointer（注意數(shù)據(jù)直接存儲(chǔ)在關(guān)鍵字之后）扔傅，關(guān)鍵字大小及數(shù)據(jù)的大小耍共，同時(shí)還含有關(guān)鍵字的一小部分實(shí)際值。
??為了高效地對(duì)數(shù)據(jù)進(jìn)行存取猎塞，這里實(shí)現(xiàn)了一個(gè)緩存系統(tǒng)试读，主要有緩存項(xiàng)cache_elem結(jié)構(gòu)和數(shù)據(jù)緩存元素data_cache_elem結(jié)構(gòu)。cache_elem中有指向?qū)嶋H的桶的指針（桶在磁盤(pán)上荠耽，用來(lái)對(duì)數(shù)據(jù)進(jìn)行定位钩骇、查找、存取等）铝量，還包含了數(shù)據(jù)緩存元素及一些標(biāo)志倘屹。數(shù)據(jù)緩存元素中指明了我們要存取的實(shí)際數(shù)據(jù)，通過(guò)內(nèi)存中的緩存系統(tǒng)慢叨，我們可以大大提高數(shù)據(jù)的存取速度纽匙。
公眾號(hào):變成之禪，專(zhuān)注CDN插爹、后臺(tái)開(kāi)發(fā)哄辣、算法和大數(shù)據(jù)请梢，歡迎關(guān)注交流
