这是一个创建于 1863 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天面试官问的问题。。我想了一下。。。
哈希索引的删除，查找应该都是 O(1)的吧？新增可能碰上哈希冲突，但如果学习 java 的 HashMap，在拉链法的基础上，当拉链拉得太长时，将拉链转换为红黑树，新增好像效率也还行吧？ O(1)+O(logn)的效率？
那是因为修改？如果修改到构成哈希索引的字段的值会导致哈希要重新计算？但如果使用时聚簇索引使用哈希，一般是建立在 ID 这种主键上的，这种主键一般都没有修改的可能吧？
如果不是增删改查性能上有优势的话理由是什么呢？
谢谢
哈希索引的删除，查找应该都是 O(1)的吧？新增可能碰上哈希冲突，但如果学习 java 的 HashMap，在拉链法的基础上，当拉链拉得太长时，将拉链转换为红黑树，新增好像效率也还行吧？ O(1)+O(logn)的效率？
那是因为修改？如果修改到构成哈希索引的字段的值会导致哈希要重新计算？但如果使用时聚簇索引使用哈希，一般是建立在 ID 这种主键上的，这种主键一般都没有修改的可能吧？
如果不是增删改查性能上有优势的话理由是什么呢？
谢谢
 | 1 mengzhexin 2020-09-18 23:51:41 +08:00 via Android  2 不支持范围锁，so 不支持事物 |
| 2 mengzhexin 2020-09-18 23:52:41 +08:00 via Android 1 拉链这种结构，不适合磁盘存储，io 也慢 |
 | 3 Newyorkcity OP @mengzhexin 感谢解答 那其实就增删改查的性能来说（假定数据都直接放在内存） 哈希索引确实是更好的？ |
 | 4 Jooooooooo 2020-09-18 23:56:34 +08:00 1 主要还是连续数据磁盘 io 和范围查询的问题 要是数据少都在内存, 那确实 hash 不错, 参考 redis |
| 5 mengzhexin 2020-09-18 23:57:14 +08:00 via Android 1 @Newyorkcity 你要是这么说，那肯定是。但就是都在内存里，也会有缺页等问题。 |
 | 6 binux 2020-09-19 00:0444 +08:00 via Android 你拿一个二叉查找树和 hash 比？ |
 | 7 xupefei 2020-09-19 00:13:50 +08:00 via iPhone 1 还有一个关键点：clustered B+ tree 在找到一个叶子结点后可以顺序扫描，不需要再从根结点查找。 应用场景就是找某一个 id 和它后面的 100 个 id 。 |
 | 8 lhx2008 2020-09-19 00:25:30 +08:00 2 hashmap 是内存很快，因为内存是你想到哪就到哪 数据库是顺序读写，每一个节点对应的是磁盘的一个页，肯定要树形的结构 |
 | 9 cassyfar 2020-09-19 03:11:50 +08:00 InnoDB 不是从内存，而是从磁盘里读取数据，所以你的那些 Big O 都是错误的。针对磁盘读取，我还没见过用 hashmap 的。。。即使是 nosql 这种 key value storage，直觉上就应该用 hashmap，也是用的 merkle tree 这种数据结构。 不过说实话，这个面试题也忒难了吧。。。感觉只有 DB 组能面。 |
 | 10 nvkou 2020-09-19 03:28:12 +08:00 via Android 依稀记得是排序和范围查找的原因。散列虽快，功能实现代价太大 |
| 12 mengzhexin 2020-09-19 07:54:45 +08:00 via Android @cassyfar 应届 总被问。甚至问磁盘文件组织结构 |
 | 13 amazingrise 2020-09-19 07:58:30 +08:00 via Android 哈希索引的话，每一个项都均匀分布在各个桶里面，要查找索引项里面的子串简直是一场灾难。如果索引是 ID 的话没什么影响，但是建立索引的不止有 ID |
 | 14 chocovon 2020-09-19 08:17:01 +08:00 via Android 关系型数据库基本上都是 B 树吧，为何要特意问 InnoDB |
 | 15 Cbdy 2020-09-19 08:27:17 +08:00 via Android InnoDB 也支持 hash 索引啊，不过是自适应的 |
 | 16 chihiro2014 2020-09-19 08:50:39 +08:00 看场景啊，如果面向内存，那么使用 hashmap 没什么可说的，性能在那边放着。如果是面向磁盘，现在不少服务器的磁盘还是机械，如果是 hashmap，它在知道信息的情况下，那么它的查找速度确实是最快的，但是要做的磁盘 I/O 的量就很大。因为是随机读取，不是循序扫描，所以它一次取的 tuple 数量可能就是一个 tuple，效率极其低下，对于全表扫描来说，反倒不如循序扫描，因为它可以一次获取一个 page 的 tuple，效率不是 hashmap 能比的。所以这时候用 B+ Tree 要来得更为合适，毕竟叶子节点上就是一个个 page，然后按着 page 去一个个读取，这样效率和速度都能大大提升，毕竟减少 IO，但提升了一次获取的量 |
Select Language