V2EX 首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐书目
黑客与画家
REWORK 简体中文版
REWORK 精装原版
深入浅出设计模式 Head First Design Patterns
代码之美 Beautiful Code
数据之美 Beautiful Data
信息论、编码与密码学
Free as in Freedom
设计原本
精通正则表达式
V2EX  ›  程序员

B+树实现磁盘存储

  •  
  •   begeekmyfriend · 5 天前 · 1385 次点击

    三年前我就想写一个关系数据库了,无奈却苦于 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)级别,电脑搞坏我全陪!

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

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

    显然 nosql 一般使用的都是哈希一类数据结构,也可以用关联式容器,但从性价比上看,哈希表是最高的。
        12
    begeekmyfriend   4 天前
    抱歉,上楼链接放错了, V2EX 不支持删除啊: http://coolshell.cn/articles/17225.html
        13
    artandlol   4 天前
    “电脑搞坏我全陪 ” 好可怕 直男不好这口
        14
    AngelCriss   4 天前 via Android
    你这个有内存泄漏啊
        15
    begeekmyfriend   4 天前
    @AngelCriss 请给出证据,我使用 valgrind 跑过的
        16
    begeekmyfriend   4 天前
        17
    ccl   4 天前
    楼主莫非是王垠?久仰呀
        18
    wangjie   4 天前
    @ccl 不是吧, 11L 的链接放错了,下面那个文章才是 lz 的
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   373 人在线   最高记录 2466   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.7.5 · 69ms · UTC 20:19 · PVG 04:19 · LAX 13:19 · JFK 16:19
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1