Fork me on GitHub

Mysql的索引有几种,时间复杂度

Mysql的索引有几种,时间复杂度

答案:MySQL主要提供2种方式的索引:B-Tree索引,Hash索引。

B树索引具有范围查找和前缀查找的能力,对于有N节点的B树,检索一条记录的复杂度为O(LogN)。相当于二分查找。

哈希索引只能做等于查找,但是无论多大的Hash表,查找复杂度都是O(1)。

显然,如果值的差异性大,并且以等值查找(=、 <、>、in)为主,Hash索引是更高效的选择,它有O(1)的查找复杂度。

如果值的差异性相对较差,并且以范围查找为主,B树是更好的选择,它支持范围查找。

MySQL中两大主要存储引擎MyISAM和InnoDB采用了不同的索引和存储策略,本文将分析它们的异同和性能。

2020-10-11 21:55:34  LeeChan 阅读(49) 评论(0) 标签:Mysql 分类:面试