V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Newyorkcity
V2EX  ›  问与答

为什么 InnoDB 选择了 B(B+)树索引而不是哈希索引?

  •  
  •   Newyorkcity · 2020-09-18 23:49:41 +08:00 · 2090 次点击
    这是一个创建于 801 天前的主题,其中的信息可能已经有所发展或是发生改变。
    今天面试官问的问题。。我想了一下。。。

    哈希索引的删除,查找应该都是 O(1)的吧?新增可能碰上哈希冲突,但如果学习 java 的 HashMap,在拉链法的基础上,当拉链拉得太长时,将拉链转换为红黑树,新增好像效率也还行吧? O(1)+O(logn)的效率?

    那是因为修改?如果修改到构成哈希索引的字段的值会导致哈希要重新计算?但如果使用时聚簇索引使用哈希,一般是建立在 ID 这种主键上的,这种主键一般都没有修改的可能吧?

    如果不是增删改查性能上有优势的话理由是什么呢?

    谢谢
    16 条回复    2020-09-19 08:50:39 +08:00
    mengzhexin
        1
    mengzhexin  
       2020-09-18 23:51:41 +08:00 via Android   ❤️ 2
    不支持范围锁,so 不支持事物
    mengzhexin
        2
    mengzhexin  
       2020-09-18 23:52:41 +08:00 via Android   ❤️ 1
    拉链这种结构,不适合磁盘存储,io 也慢
    Newyorkcity
        3
    Newyorkcity  
    OP
       2020-09-18 23:54:16 +08:00
    @mengzhexin 感谢解答 那其实就增删改查的性能来说(假定数据都直接放在内存) 哈希索引确实是更好的?
    Jooooooooo
        4
    Jooooooooo  
       2020-09-18 23:56:34 +08:00   ❤️ 1
    主要还是连续数据磁盘 io 和范围查询的问题

    要是数据少都在内存, 那确实 hash 不错, 参考 redis
    mengzhexin
        5
    mengzhexin  
       2020-09-18 23:57:14 +08:00 via Android   ❤️ 1
    @Newyorkcity 你要是这么说,那肯定是。但就是都在内存里,也会有缺页等问题。
    binux
        6
    binux  
       2020-09-19 00:04:44 +08:00 via Android
    你拿一个二叉查找树和 hash 比?
    xupefei
        7
    xupefei  
       2020-09-19 00:13:50 +08:00 via iPhone   ❤️ 1
    还有一个关键点:clustered B+ tree 在找到一个叶子结点后可以顺序扫描,不需要再从根结点查找。
    应用场景就是找某一个 id 和它后面的 100 个 id 。
    lhx2008
        8
    lhx2008  
       2020-09-19 00:25:30 +08:00   ❤️ 2
    hashmap 是内存很快,因为内存是你想到哪就到哪
    数据库是顺序读写,每一个节点对应的是磁盘的一个页,肯定要树形的结构
    cassyfar
        9
    cassyfar  
       2020-09-19 03:11:50 +08:00
    InnoDB 不是从内存,而是从磁盘里读取数据,所以你的那些 Big O 都是错误的。针对磁盘读取,我还没见过用 hashmap 的。。。即使是 nosql 这种 key value storage,直觉上就应该用 hashmap,也是用的 merkle tree 这种数据结构。

    不过说实话,这个面试题也忒难了吧。。。感觉只有 DB 组能面。
    nvkou
        10
    nvkou  
       2020-09-19 03:28:12 +08:00 via Android
    依稀记得是排序和范围查找的原因。散列虽快,功能实现代价太大
    xupefei
        11
    xupefei  
       2020-09-19 03:56:05 +08:00 via iPhone
    @cassyfar 这题难度不高吧。B 树算是数据库原理的基础知识,科班出身都应该知道的。
    mengzhexin
        12
    mengzhexin  
       2020-09-19 07:54:45 +08:00 via Android
    @cassyfar 应届 总被问。甚至问磁盘文件组织结构
    amazingrise
        13
    amazingrise  
       2020-09-19 07:58:30 +08:00 via Android
    哈希索引的话,每一个项都均匀分布在各个桶里面,要查找索引项里面的子串简直是一场灾难。如果索引是 ID 的话没什么影响,但是建立索引的不止有 ID
    chocovon
        14
    chocovon  
       2020-09-19 08:17:01 +08:00 via Android
    关系型数据库基本上都是 B 树吧,为何要特意问 InnoDB
    Cbdy
        15
    Cbdy  
       2020-09-19 08:27:17 +08:00 via Android
    InnoDB 也支持 hash 索引啊,不过是自适应的
    chihiro2014
        16
    chihiro2014  
       2020-09-19 08:50:39 +08:00
    看场景啊,如果面向内存,那么使用 hashmap 没什么可说的,性能在那边放着。如果是面向磁盘,现在不少服务器的磁盘还是机械,如果是 hashmap,它在知道信息的情况下,那么它的查找速度确实是最快的,但是要做的磁盘 I/O 的量就很大。因为是随机读取,不是循序扫描,所以它一次取的 tuple 数量可能就是一个 tuple,效率极其低下,对于全表扫描来说,反倒不如循序扫描,因为它可以一次获取一个 page 的 tuple,效率不是 hashmap 能比的。所以这时候用 B+ Tree 要来得更为合适,毕竟叶子节点上就是一个个 page,然后按着 page 去一个个读取,这样效率和速度都能大大提升,毕竟减少 IO,但提升了一次获取的量
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4599 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 08:05 · PVG 16:05 · LAX 00:05 · JFK 03:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.