V2EX 首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

B+树实现磁盘存储

  •  
  •   begeekmyfriend · 217 天前 · 2312 次点击
    这是一个创建于 217 天前的主题,其中的信息可能已经有所发展或是发生改变。

    三年前我就想写一个关系数据库了,无奈却苦于 B+树算法的实现,如今数据库仍旧没着落,但总算写出 B+树实现了磁盘落地。虽然只是个 demo ,但算法上保证完备,实践上经久耐操,对百万级样本处理达到秒级性能。附上源码以及测试用例(包括文件落地和读写),望数据库和存储大牛们切磋指教!

    https://github.com/begeekmyfriend/bplustree

    一种玩法: 随机生成一百万样本和四百万条 CRUD 指令,将结果存储到/tmp/data.bp/tmp/metadata.bp

    ./coverage_build.sh
    

    退出后再次运行 demo ,读取默认保存的/tmp/data.bp/tmp/metadata.bp

    ./demo_build.sh
    

    使用 dump 指令在终端上画出整个树形结构(见 help 输出)

    注意:下次玩的时候记得更改文件名,否则会把文件中原有的数据读入

    顺便说一句,代码质量基本属于principle(al)级别,电脑搞坏我全陪!

    22 回复  |  直到 2017-09-20 14:30:43 +08:00
        1
    shoaly   217 天前
    样本在哪里?
        2
    shoaly   217 天前
    sorrry...........眼睛太瞎 找到了
        3
    svenFeng   217 天前 via Android
    。。。 B+树的索引有这么难么。。。感觉就是细节比较多吧
        4
    micyng   217 天前   ♥ 1
    大概 1 个月前验证过楼主的代码,跟 http://www.cs.usfca.edu/~galles/visualization/BPlusTree.html 结果稍微有些不一样
        5
    svenFeng   217 天前 via Android
    丢一个自己写的垃圾 rdbms[sdb]( https://github.com/svenFeng/sdb/blob/master/readme.md)(逃
        6
    svenFeng   217 天前 via Android
    链接错了😂😂😂https://github.com/svenFeng/sdb
        7
    wlee1991   217 天前 via iPhone
    我不会再给任何公司工作。我会创造一个伟大的公司,它会创造世界上最精致的产品,它会给真正有价值的人相应的回报和尊重。

    seriously ???
        8
    lbp0200   217 天前 via Android
    可以实现 nosql ,比如 key 、 value
        9
    begeekmyfriend   217 天前
    @micyng 主要还是节点分裂点的选择不一样,比如我一向是(len + 1) / 2 ,而他则有时这样,有时又是 len / 2 ,导致结构不一样,但不影响效果和效率。另外我仍然保留了内存版,你可以观察效果,并且随意设置节点大小,比如把叶子设置得比非叶子更大一点: https://github.com/begeekmyfriend/bplustree/tree/in-memory
        10
    begeekmyfriend   217 天前
    @lbp0200 nosql 原本不需要 B+树,你看 redis 实现过吗? B+树本来就是为 SQL 实现的,它比 B 树的优势在于范围查询更快,因为数据都在叶子节点上,所有的叶子节点又在同一底层上
        11
    begeekmyfriend   217 天前
    我在一篇博文 http://www.yinwang.org/blog-cn/2017/04/17/management-tricks 写到:“索引的存储又分为有序和无序,前者使用关联式容器,比如 B 树,后者使用哈希算法。这两类算法各有优劣:比如,关联式容器时间复杂度稳定 O(logN),且支持范围查询;又比如哈希算法的查询、增删都比较快 O(1),但这是在理想状态下的情形,遇到碰撞严重的情况,哈希算法的时间复杂度会退化到 O(n)。”

    显然 nosql 一般使用的都是哈希一类数据结构,也可以用关联式容器,但从性价比上看,哈希表是最高的。
        12
    begeekmyfriend   217 天前
    抱歉,上楼链接放错了, V2EX 不支持删除啊: http://coolshell.cn/articles/17225.html
        13
    artandlol   217 天前
    “电脑搞坏我全陪 ” 好可怕 直男不好这口
        14
    AngelCriss   216 天前 via Android
    你这个有内存泄漏啊
        15
    begeekmyfriend   216 天前
    @AngelCriss 请给出证据,我使用 valgrind 跑过的
        16
    begeekmyfriend   216 天前
        17
    ccl   216 天前
    楼主莫非是王垠?久仰呀
        18
    wangjie   216 天前
    @ccl 不是吧, 11L 的链接放错了,下面那个文章才是 lz 的
        19
    sunny123   111 天前
    楼主,你好,请问我打算 key 放手机号,用了 long 类型的数据类型输出还是错误,没法正常输出正常的手机号,unsigned long 好像只能输出最大值,代码有些地方还是看不太懂,key 放数组型进行比较是不是比较麻烦,能不能请楼主指导一下
        20
    begeekmyfriend   105 天前 via Android
    @sunny123 抱歉回复晚了,应该可以的,你打算用定长还是变长数组?
        21
    sunny123   65 天前
    @begeekmyfriend 好久没来了,感谢回复,问题已解决,用的 string 形式的 key
        22
    begeekmyfriend   65 天前
    @sunny123 用 C++写的么,发展的怎样了,前端用了 SQL 没:-)
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   2583 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.0 · 70ms · UTC 07:33 · PVG 15:33 · LAX 23:33 · JFK 02:33
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1