索引：用于提升数据库的查找速度

索引是建立得越多越好吗   （No）
➢数据量小的表不需要建立索引,建立会增加额外的索引开销
➢数据变更需要维护索引,因此更多的索引意味着更多的维护成本
➢更多的索引意味着也需要更多的空间
 

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

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

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

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

 

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

 

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

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

select * from t where name=”shenjian”;

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

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

    分组：group by

    排序：order by

    比较：<、>

   范围查找

…

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

并且   最重要的是   InnoDB并不支持哈希索引。

 

 

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

先简单介绍下几种树。

第一种：二叉搜索树

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

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

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

第二种：B树

B树，它的特点是：

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

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

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

第三种：B+树

B+树，仍是m叉搜索树，在B树的基础上，做了一些改进：

(1)非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；

     B+树中根到每一个节点的路径长度一样，而B树不是这样。

(2)叶子之间，增加了链表，获取所有节点，不再需要中序遍历，这些改进让B+树比B树有更优的特性。

 

总结

数据库索引用于加速查询

虽然哈希索引是O(1)，树索引是O(log(n))，但SQL有很多“有序”需求，故数据库使用树型索引

InnoDB不支持哈希索引

另外：虽然都是B+树，但是InnoDB和MyISAM的索引实现也有差异，可以查看我的上一篇博客。