kvdb

介绍

kvdb是一个基于B+ Tree的简单KV数据库。这不是一个实用的项目，主要目的是学习B+ Tree的应用。

软件架构

软件架构说明详见 doc/design.ppt。

安装教程

1. 先下载代码到你本地，现在只支持Linux。

   git clone git@gitee.com:mphyatyh/kvdb.git

2. 编译

   cd kvdb/src

   make

   编译完成之后，在这个目录下应该有如下两个文件：

   kv -- 用于测试的命令行程序

   libkvdb.so -- 这个是这个数据库的动态链接库文件。

使用说明

1. 简单测试，可以用命令行程序kv执行插入、删除、查找等操作。

   kv help                   -- this message
   kv get <key>              -- get a key
   kv put <key> <val>        -- set key
   kv del <key>              -- delete a key
   kv list                   -- list all key in the db
   kv ins <start_seq> <num>  -- insert records in batch mode
   kv clr                    -- remove all records in the database
   kv verify                 -- get all records and verify them

上面是kv支持的命令，说明如下：

• kv get

  ​ 查找一个key

• kv put

  ​ 插入或者更新一条记录

• kv del

  ​ 删除一条记录

• kv list

  ​ 列出数据库中所有记录。

• kv ins <start_seq>

  ​ 批量插入记录，start_seq是起始的序号。这个命令在插入记录的时候，用key = crc64(start_seq + i)作为key，用value = crc64(key)作为值。这样做的目的有两个：（1）用顺序的序号seq来产生伪随机的key，这样可以模拟真实的随机插入。（2）用key的crc64值作为value，这样可以在插入之后读出这个value与key的crc64值比较做校验。

• kv clr

  清空所有记录，尚未实现。

• kv verify

  校验数据库中用kv ins命令插入的所有记录，尚未实现。

2. 在其他App中调用kvdb提供的API。

   • kvdb_t

   struct kvdb_s;
   typedef struct kvdb_s *kvdb_t;

上面的kvdb_t是数据的描述符，这个描述符代表一个数据库文件，通过调用kvdb_open可以得到一个描述。在一个应用程序中可以同时打开多个数据库文件。以后的get/put/del等操作都需要用到这个描述符，数据库用完之后，需要调用kvdb_close关闭这个库文件。

 kvdb_t kvdb_open(char *name);
 int kvdb_close(kvdb_t db);
 int kvdb_get(kvdb_t db, uint64_t k, uint64_t *v);
 int kvdb_put(kvdb_t db, uint64_t k, uint64_t v);
 int kvdb_del(kvdb_t db, uint64_t k);

• kvdb_open - 打开数据库文件。
• kvdb_close - 关闭数据库文件。数据用完之后，必须关闭文件，否则可能会出现丢数据的情况。
• kvdb_get - 在数据库查找key为k的记录。如果找到返回0，并把value存放到v中。如果没找到，返回-1。
• kvdb_put - 把key和value分别为k和v的记录存放到数据库中。如果k已经存在，则更新它的v。否则新增一条记录。
• kvdb_del - 删除key为k的记录。

    struct cursor_s;
    typedef struct cursor_s *cursor_t;
    cursor_t kvdb_open_cursor(kvdb_t db, uint64_t start_key, uint64_t     end_key);
    int kvdb_get_next(kvdb_t db, cursor_t cs, uint64_t *k, uint64_t *v);
    int kvdb_del_next(kvdb_t db, cursor_t cs, uint64_t *k, uint64_t *v);
    void kvdb_close_cursor(kvdb_t db, cursor_t cs);

上面的函数时用来执行批量操作的：（1）查找key在一个范围内的所有记录；（2）删除key落入一个范围内的所有记录。注意：范围包括start_key，但不包括end_key。

kvdb_del_next() -- 这个函数还没有实现。

性能测试

插入性能，1000万条记录，耗时700sec。平均插入每条记录耗时70us。

total: 9983000 in 700 sec, avarage: 70 us/record
last 1 sec: 15500, avarage: 64 us/record
total: 9998300 in 701 sec, avarage: 70 us/record
last 1 sec: 15300, avarage: 65 us/record

参与贡献

1. Fork 本仓库
2. 新建 Feat_xxx 分支
3. 提交代码
4. 新建 Pull Request