数据库索引原理

之前去到携程面试的时候遇到面试数据库索引原理的问题特在此记录一下

以mysql为例,主要使用hash或者b+tree来实现索引的存储

Q1 : hash索引是什么

hash结构存储 : 很简单,就是利用hash算法实现索引查找,hash索引的特点是无法实现范围查找,因为本身hash算法就是实现key-value式的对应,还有就是hash的查找效率很高,时间复杂度应该是O(1)

Q2 : B+tree索引是什么

B+tree结构 : 类似于二叉树的存储,算法逻辑上来讲二叉树的查找效率为O(logn),用二叉树存储应该最好,但是实际情况中为了减少磁盘IO的操作数而采用b-tree来存储文件,因为二叉树的最坏结果,磁盘IO的操作数可能就是二叉树的高度,所以最好降低二叉树的高度,B-tree实际的操作数据不比二叉树少,但是B-tree有一部分操作是内存中的比较操作来取代磁盘IO操作,所以可以提高实际的查找效率

Q3 : 什么是聚集索引什么又是非聚集索引

聚集索引 : 聚集索引将会决定数据在磁盘中的物理顺序,该索引一张表只有一个,一般就是主键,所以这就是为什么每张表都应该有一个主键。

非聚集索引 : 通常意义情况下的索引,独立于数据存在,只包含被建立索引的数据,以及一个行定位符,可以理解为一个聚集索引物理排序的指针,通过这个指针,可以找到行数据

Q4: 什么是联合索引以及特点

联合索引:多个字段上建立的索引,能够加速符合查询条件的检索,满足最左前缀原则 a,b,c 满足a | a,b |a,b,c

Q5 : 什么是覆盖索引

覆盖索引 : 如果查询的数据在索引中存在,则直接返回而不会再查询(一般以联合索引实现)

---未完待续