一个简单的key-value存储系统的实现 - 面向对象网,数据库,基础,原理,学习,对象 - 面向对象技术开发

面向对象技术开发

会员投稿 投稿指南 站长资讯通告:
您的位置: 首页 > 数据库 > 其它数据库 > 正文

一个简单的key-value存储系统的实现

来源: www.bianceng.cn 阅读:

\

正文:

所谓的Key-Value就是每次存储一个数据时,是根据Key进行索引存储的。为了实现 Key的快速查找功能,我使用了B-tree存储结构。B-tree被大量用于数据库的索引中,所以选 用B-tree想必不会有太大的问题。Value是对应该Key的值,他的长度是未知的,所以要实现 这样一个存储系统,必须要解决从Key值到文件位置的映射关系。

问题一:实现文件 的"自由"读写
问题二:实现BTree

问题一:实现文件的"自由 "读写。

基本思想:所有内容被存储到一个文件中,文件被划分成同一大小的粒度, 可以自由的申请不同的大小空间,可以释放已经申请的空间。使得文件操作可以和内存操作 接口一致。

基于上述的需求,我的文件存储结构如下图所示:

\

typedef struct _diskatom{
    int64 self;    //自身索引
    int64 next;    //下一索引
    int64 pre;    //前一索引
    int64 ext;    //扩展索引
    int size;    //大小
    unsigned char info;    //信息[1:HEAD|1:USED|0|0|0|0|0|0]
    unsigned char dirty;
    unsigned char data[DISK_ALLO_SIZE];
}diskatom_t;
    
typedef struct _diskctx{
    int64 ctxtop;
    int64 num_used;
    int64 num_free;
    diskatom_t list_used;
    diskatom_t list_free;
}diskctx_t;

申请空间:

1. 计算申请大小需要几块空间。

2. 检查空闲列表 中是否有足够的空间。

3. 存在足够的空闲块,将空闲块移动至"使用列表"。

4. 空闲空间不足,扩充文件大小,将新增块插入"使用列表"。

释放空间:

正好和申请空间相反。

1. 将使用块移动至"空闲列表"。使得该块可以被重 新申请。

处理申请空间和释放空间外,还实现了读,写,重新申请空间功能。

问题二 :实现BTree

摘录百科百科对BTree的描述:

B-tree(多路搜索树,并不是二叉的)是 一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加 快存取速度。按照翻译,B通常认为是Balance的简称。这个数据结构一般用于数据库的索引 ,综合效率较高。

http://baike.baidu.com/view/363832.htm

我们有了上面(问题一)的读写文件的功能,那么将B-tree建立到文件中去,和将之建立到 内存,其实是一样的。B-tree的内容在网上都可以找到。只不过在操作节点的内容时,我们 可能要去读写文件。原来在内存中的指针,现在变成了在文件中的位置。

测试 功能:

现在软件实现了以下的功能,用于操作Key-value数据库。在效率方面,写1万个数 据大致在350ms吧,查找读取的速度比写快一倍左右;由于是直接写硬盘,没有缓存机制,效 率也只能这样。先把功能实现了再优化吧。

open( dbpath )        打开一个数 据库

set( container, key, value )  增加/设置一个Key

get( container, key )       获取一个Key的内容

del( container, key )      删除一个 Key

close( )            关闭一个数据库

源码下载: http://files.cnblogs.com/linxr/kvfs.rar

Tags:
相关文章列表: