数据库索引，到底是什么做的？

问题1. 数据库为什么要设计索引?

图书馆存了1000W本图书，要从中找到《架构师之路》，一本本查，要查到什么时候去？

于是，图书管理员设计了一套规则：

(1)一楼放历史类，二楼放文学类，三楼放IT类…

(2)IT类，又分软件类，硬件类…

(3)软件类，又按照书名音序排序…

以便快速找到一本书。

与之类比，数据库存储了1000W条数据，要从中找到name=”shenjian”的记录，一条条查，要查到什么时候去？

于是，要有索引，用于提升数据库的查找速度。

问题2. 哈希(hash)比树(tree)更快，索引结构为什么要设计成树型？

加速查找速度的数据结构，常见的有两类：

(1)哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)；

(2)树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(lg(n))；

可以看到，不管是读请求，还是写请求，哈希类型的索引，都要比树型的索引更快一些，那为什么，索引结构要设计成树型呢？

*画外音：80%的同学，面试都答不出来。*

索引设计成树形，和SQL的需求相关。

对于这样一个单行查询的SQL需求：

select * from t where name=”shenjian”;

确实是哈希索引更快，因为每次都只查询一条记录。

*画外音：所以，如果业务需求都是单行访问，例如passport，确实可以使用哈希索引。*

但是对于排序查询的SQL需求：

• 分组：group by
• 排序：order by
• 比较：
• …

哈希型的索引，时间复杂度会退化为O(n)，而树型的“有序”特性，依然能够保持O(log(n)) 的高效率。

任何脱离需求的设计都是耍流氓。

多说一句，InnoDB并不支持哈希索引。

问题3. 数据库索引为什么使用B+树？

为了保持知识体系的完整性，简单介绍下几种树。

第一种：二叉搜索树

 

 

 

二叉搜索树，如上图，是最为大家所熟知的一种数据结构，就不展开介绍了，它为什么不适合用作数据库索引？

(1)当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢；

(2)每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO；

*画外音：这个树经常出现在大学课本里，所以最为大家所熟知。*

第二种：B树

 

 

 

B树，如上图，它的特点是：

(1)不再是二叉搜索，而是m叉搜索；

(2)叶子节点，非叶子节点，都存储数据；

(3)中序遍历，可以获得所有节点；

*画外音，实在不想介绍这个特性：非根节点包含的关键字个数j满足，(┌m/2┐)-1