# kvdb

**Repository Path**: codinghuang/kvdb

## Basic Information

- **Project Name**: kvdb
- **Description**: 一个基于B+ Tree的简单KV数据库。这不是一个实用的项目，主要目的是学习B+ Tree的应用。
- **Primary Language**: C
- **License**: BSD-2-Clause
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 36
- **Created**: 2021-02-18
- **Last Updated**: 2021-02-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 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> 

     ​	查找一个key

   * kv put <key> <value>

     ​	插入或者更新一条记录

   * kv del <key>  

     ​	删除一条记录

   * kv list

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

   * kv ins <start_seq> <num>

     ​	批量插入记录，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 

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

```c
 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的记录。



```c
    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