【你问我答】MySQL索引为什么大多使用b+树来存储？

问题描述：

MySQL索引大多使用b+树，为什么不用哈希map来存储？

回答有奖：

选取一位认真回答问题的牛友，赠送200牛币！

▶回答尽量有自己的思考，不要单纯的只是复制粘贴定理定义，或者他人blog哦~

Tips.牛币兑换中心

你问我答问题汇总：点击进入

关注你问我答栏目：点击关注

你问我答 - 答问题，成大佬，拿牛币！

你问我答是牛客新栏目，每周1期几个面试中真实遇到的问题，

牛友在问题贴下留下自己的知识，经验与见解，

帮助更多牛友了解更多技术相关知识！

#悬赏##Java工程师##面试题目##春招##校招#

全部评论

推荐最新楼层

又戈月空

门头沟学院产品经理

hash虽然可以快速定位，但是没有顺序，IO复杂度高。如果只选一个数据，那确实是hash更快。但是数据库中经常会选择多条，这时候由于B+树索引有序，并且又有链表相连，它的查询效率比hash就快很多了。而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。 hash表只能匹配是否相等，不能实现范围查找，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索。当需要按照索引进行orderby的时候，hash值没办法支持排序，因为hash散列的特性，无法利用索引完成排序。组合索引可以支持部分索引查询，如（a，b，c）的组合索引，查询中只用到了a和b也可以查询，如果使用hash表，组合索引会将几个字段合并hash，没办法支持部分索引。当数据量很大的时候，hash冲突的概率也很大，特别是在有大量重复键值的情况下，哈希索引的效率是非常低的，因为存在哈希碰撞问题。

1 回复分享

发布于 2020-04-07 19:32

offer快到碗里来呢

门头沟学院 Java

谁说mysql没有hashmap，点开MySQL可以看到两种存储，b+数和hashmap,只是很少用，因为hashmap不支持范围查找，有hash冲突

1 回复分享

发布于 2020-04-07 18:35

白驹之过隙

北京市海淀区简明教育培训学校 Java

对比下两者的优劣哈希表：keys——>hash算法——>固定长度的keys地址存在数据碰撞问题，hash算法对不同的key可能会计算出相同的结果。这就需要链地址法把碰撞的数据连接起来，计算哈希值后还需要检查该哈希值是否存在碰撞数据链表，有则一直遍历到链表尾部，直到找到真正的key对应数据为止。哈希算法的时间复杂度为O(1)，所以检索速度很快。但对于范围查找的数据检索则无法给出固定的key。 B+树是建立在B树的基础上，区别是B树一个节点里存储的是数据，而B+存储的是索引地址，B+树的叶子节点存所有的数据。 B树和B+树的时间复杂度取决于树的高度，减少了磁盘的IO，支持范围查找。 B+树存储的索引，所以即使在节点有限容量的情形下也可以存储大量的索引使树的高度降低，B+树的叶子节点是数据阶段用一个链表串联起来便于范围查找。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

点赞回复分享

发布于 2020-04-11 07:23

_马可_

0 材料员

通常B+数据的查询时间为log(n),而利用Hash时间为o(1)，那为什么还要用B+树呢。对于B+树，相比于Hash好处： 1.利用Hash需要把数据全部加载到内存中，如果数据量大，是一件很消耗内存的事，而采用B+树，是基于按照节点分段加载，由此减少内存消耗。 2.和业务场景有段，对于唯一查找（查找一个值），Hash确实更快，但数据库中经常查询多条数据，这时候由于B+数据的有序性，与叶子节点又有链表相连，他的查询效率会比Hash快的多。

点赞回复分享

发布于 2020-04-08 18:50