1.索引是什么?

索引是一种用于数据库高效获取数据的数据结构！
以下讨论主要基于InnoDB存储引擎！

首先需要注意的是InnoDB存储引擎表就是索引组织表！即在InnoDB中数据即索引，索引即数据。而这个存储引擎表（索引表)中的数据是按照主键顺序排列。将聚集索引的叶子节点称为数据页

2.索引结构分类

主要有两种数据结构——哈希索引和B树索引（尤以B+树为主）

• 哈希索引：不必多说，哈希索引即根据哈希算法将目标字段的key转为数组的下标，进而一步定位到目标数据进而获得值。

  InnoDB引擎支持哈希索引是自适应的，会根据表的使用情况自动为表生成哈希索引，而不能人为干预是否生成哈希索引！言外之意，InnoDB不能显示的创建哈希索引，下图可知
  

• B+树索引是现在主流数据库系统中最经常用到和最为有效的索引，其结构类似二叉树，又高于二叉树

  B+树中的B代表的是Balance，即平衡之意，由最早的平衡二叉树(AVL)演化而来！

• 全文索引
  虽然在数据库总使用 like + % 就可以实现大部分的模糊查询，但这种情况终究还是受限于数据量，当数据量大的时候效率是极其低下的！所以全文索引就应运而生.
  全文索引通常使用倒排索引来实现。即单词 ——> 位置的形式

  通过数值比较、范围过滤等就可以完成绝大多数我们需要的查询，但是，如果希望通过关键字的匹配来进行查询过滤，那么就需要基于相似度的查询，而不是原来的精确数值比较。全文索引就是为这种场景设计的。

3.索引结构对比

B+树索引和哈希索引的区别：

• 等值查询，哈希索引明显有绝对优势
• 哈希索引不支持范围查找，而B+树支持
• B+树可以很好地应对排序等查询
• 在有大量重复键值情况下，由于哈希碰撞其效率也是极低的

4.B+树索引

4.1 B树

我们可以先来看下B树

因为内存的易失性。一般情况下，我们都会选择将数据库表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。
另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。
如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。
平衡二叉树是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？
可以想象到二叉树的节点将会非常多！高度也会极其高！我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！

总结来收，就是因为不论什么样的二叉树，在海量数据面前，整个树的结构变得极其瘦高！查询效率非常低下，因为需要多次访问磁盘数据块（页），代价昂贵。因此就引出以下B树这种结构

节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的基本单位都是页，所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。

B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。这样一来，数据的查询效率就比一般的二叉树高！

4.2 B+树

简单来讲，B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树种，所有记录节点都是按照键值的大小顺序存放在同一层叶子节点上的，由各叶子节点双向指针进行连接！

4.3 B树和B+树的对比

• B 树节点中不仅存储键值，也会存储数据；而 B+ 树非叶子节点上是不存储数据的，仅存储键值

  之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。
  即 B+ 树拥有高扇出性！
  B+ 树的阶数是等于结点键值最多的数量

• B+ 树索引的所有数据均存储在叶子节点，而且结点之间有双向链表，结点内部也是双向链表，高效的支持范围查找和排序查找！

上图中的 B+ 树索引就是 InnoDB 中 B+ 树索引真正的实现方式，准确的说应该是聚集索引
MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。即非聚集索引

延申一 : 扇入和扇出

• 扇入：是指直接调用该模块的级模块的个数。扇入大表示模块的复用程序高。

• 扇出：是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高，需要控制和协调过多的下级模块；但扇出过小（例如总是1）也不好。

如果你看到这了就不妨继续往下看吧！

4.4 B+树索引之聚集索引和非聚集索引

刚刚我们介绍完了B+树索引的数据结构，也知道了InnoDB存储引擎采用的是B+树索引，并且叶子节点存放的是键值和和数据，即聚集索引！那么聚集索引和非聚集索引到底是什么呢?

本作品采用《CC 协议》，转载必须注明作者和本文链接