1.B+树查找一条时间复杂度为（O(logn)）,而hash为O(1)，忽然hash比B+快，为什么数据库存储还是用B+树？
答：（1）因为和业务场景有关。如果只选一个数据，那确实是hash更快。但是数据库中经常会选择多条，这时候由于B+树索引有序，并且又有链表相连，它的查询效率比hash就快很多了。
（2）而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。
2.红黑树为什么这样设计？
答：（1）红黑树和二叉搜索树一样，是左小右大，但是二叉搜索树会出现极端情况。当插入一个有序序列，会导致树一端过大，二叉搜索树会退化成有序链表，红黑树的调整行为就是为了是树始终维持一个平衡。
（2）红黑树为什么要维持平衡要结合他的使用场景，红黑树应用在TreeSet和HashMap（数组+链表+红黑树），这两个应用红黑树是为了较小搜索时间，二叉树的高度越低则查找越快。
京公网安备 11010502036488号