说完索引底层是b+树以后，说既然B+树有这么多好处，为什么hashmap底层选择红黑树而不是B+树?

从来没想过这问题，憋了半天屁都放不出来

msyql为什么选择B+树？是因为mysql操作的都是硬盘，硬盘是IO操作，IO是一种很消耗资源的操作，那么这个时候B+树的优势就出来了， 它是一种胖树，就是说树的高度一般就三层，对应三次IO，IO次数少，效率高，当然还有mysql无法一次加载完所有数据，需要按页加载以及叶子结点的链表有序等等。
hashmap为什么选择红黑树？是因为hashmap更多的是用来进行内存操作，内存操作效率高，这个时候B+树反而就不合适了，假如hashmap也用B+树，在进行查找的时候，最多进行三次树的深度查询，之后就要遍历了，这对应内存的高效操作来说，没有加深深度的效率来得高，比如在取一个值得时候，hashmap的时间复杂度为O1，而B+树比O1大，具体我也算不来，应该是O(log n)
等等等等，顺着这个思路往下说吧，这是我这半年背八股文总结的，不对的话，望楼下轻喷

可能是b+树插入和删除节点涉及到节点的分裂和合并，与红黑树相比，效率更低，因为需要频繁插入和删除操作

b+树和b树是多叉树，索引用它们多叉树可以减少磁盘的io。
hashmap主要是红黑树与avl树(平衡二叉树）与树堆对比吧，树堆可能会变成链表，性能会变差，不稳定。avl树每次插入和删除都要调整，很耗性能。红黑树只是相对平衡，不需要每次插入或者删除都要调整，比树堆稳定，比avl树不耗性能。
有错误请楼下指出

理解不够呢，红黑树是平衡树，好处是平衡，保证对数复杂度。b+树是多叉树，好处是深度小，io少

这种问题其实结合使用场景想一想就好了，你现在想不明白这个，以后还会被“既然跳表的效率这么高，那为什么MySQL不用跳表而用B+树”难倒。

都在内存里搞什么b+啊，再说一个树内容有8个都逆天了

不谈薪资的问题都是刷流氓 -_-

首先HashMap底层就不是红黑树，是链接法解决冲突的散列表
用红黑树的那是TreeMap
红黑树实现起来比B+树简单，在内存中进行二分查找没有什么数据结构能比的过二叉排序树了，红黑树就是自动维护平衡的二叉排序树，在红黑树里查找一个目标从头到尾都在进行二分查找，而B+树查找过程更为复杂。B+树是为了磁盘而生的，我们都应该知道磁盘I/O是相当慢的，比内存中进行操作慢数个数量级，B+为减少磁盘的读取次数，增大每个内部节点内存储元素的个数。B+树的内部节点通常存储在一个盘块中，一个内部节点里的所有元素是连续的。虽然机械硬盘可以进行随机访问，但效率远不如从一点开始进行连续物理地址的读取。原因是需要通过硬盘磁头的移动去寻找随机的地址。如果是访问连续的数据，磁头不需要移动，只需要跟随盘面的高速旋转就能很快地完成数据的读取；如果是要依次查找ABCDE几个不连续但先后顺序和盘面旋转顺序一致的地址，根据一般的磁头调度算法，也能在盘面转完一圈内读取完毕，但如果要进行二分查找，地址顺序可能就是CAB，可能先前进再后退，这就需要磁盘根据读取数据方向的变换完成数圈的旋转才能查找到目标元素。
所以在B+树存储在磁盘上的内部节点中（可以看做一个排序好的数组）进行二分查找代价可能远远高于顺序查找，故而一般的B+树实现中，在内部节点内进行的都是顺序查找。
虽然B+树高度比红黑树低很多，但因为有了局部的顺序查找，性能自然会比全程二分查找慢。TreeMap是完全工作在内存中的，在内存中进行随机地址访问是极快的，所以才能充分发挥出二分查找的优势，故而TreeMap使用红黑树而不使用B+树。
其次，由于B+树内部节点是连续排序的数组，所以在其中进行数据的插入或删除，时间开销就如同数组O(N)的元素插入与删除，是相当慢的，跟红黑树的O(log2N)链接插入肯定是比不了的。
顺便题外话，B+树要完成内部节点中元素的插入与删除通常将会整个内部节点拷贝到内存中再进行操作，操作完后再写到磁盘上。

@纯音乐纯音乐
设对于存储字符串作为key的场景，共存储M条字符串，平均每条字符串长度为N
HashMap的时间复杂度取决于哈希函数的时间复杂度，对于刚才所设的字符串场景那么时间复杂度应该平均为(N)/*忘了平均复杂度是哪个符号了，但不是大O*/。
红黑树中的查找复杂度O(2log2(M))/*AVL是严格的O(log2(M))*/，但每次查找都进行的是字符串的大小比较。易知，不严格的说，第一次/*在红黑树的第一层*/比较发生在字符串的0号位，第二次/*在红黑树第二层*/比较会从0号位开始比较到字符串的1号位，第三次可能会从0比较到2号位...，最坏情况下，如同
ABCDEF
ABCDEG
两个长度N=6的字符串，需要比较
1+2
+3
+4+5+6 = (1 + 6) * 6 / 2 = 21 = (7/2)N ≈ (N/2) x N 次
在这个式子中，N/2应该是假设存储的是多数长度为N的字符串，平均在每条字符串的比较字符的次数，而后面的N是要比较的字符串的条数，所以在红黑树里后面的N应该替换成M
故红黑树对于字符串的查找时间复杂度应该是
O((N/2) x 2log2(M)) = O(Nlog2(M))
平均情况下，比起哈希表的 N 会多一个log2(M)的因子。不过红黑树好处就是稳定，哈希表存在冲突和扩容等影响性能的因素

高司令:有本事冲我来，hashmap是我写的，别刁难我徒弟们。 一个月才几百块，996别人睡觉了他们才下班，混碗饭而已，你玩什么命啊。

这时常见面试题，多看点面经就会发现者道题经常出现了，还会问你什么是红黑树，和AVL树有什么不同，类似的问题还有很多

b+是有序的，hashmap的hash值是无序的