文章目录
- 一、索引的本质
- (一)为什么数据库的索引不能用二叉搜索树？
- (二)为什么红黑树不适合数据库索引？
- (三)聚集索引和非聚集索引
- 二、MySQL中索引的实现（摘）
- （一）MyISAM索引实现：
- （二）InnoDB索引实现：
一、索引的本质
索引是帮助MySQL高效获取数据的排好序的数据结构。
如上图所示这个表，如果没有索引的话，当我们执行查询的时候：
select * from table1 where Col2 = 23;
就会从头比较到尾，然后找到对应的，一共需要查找7次，索引很慢。
索引的作用就在这了，可以快速的帮你找到某列上要找的元素。
假设，我们为Col2建立上索引：
并假设我们的索引是一颗二叉排序树（真实的数据库底层并不是使用二叉排序树的，这里只是做一个简单的演示例子）。
可以看到这是一颗二叉排序树，时间复杂度是和二分查找差不多的。每次都可以舍掉一半的数据。
当我们再次执行：
select * from table1 where Col2 = 23;
- 1、先跟34对比，比34小，查找34的左⬅️子树；
- 2、跟22对比，比22大，查找22的右➡️子树；
- 3、跟23对比，与23相等，返回这行结果。
可以看到一共查找了3次。
如果数据量很大的话，其实优势就体现出来了。
(一)为什么数据库的索引不能用二叉搜索树？
根据上面的演示，看着二叉搜索树也是可以的呀，也挺快嘛。 但是为什么用在数据库底层不合适呢？这也是面试时常问的。
我们可以演示一下： https://www.cs.usfca.edu/~galles/visualization/BST.html
我们假设我们给Col1加上索引，那么依次对二叉搜索树插入：1、2、3、4、5、6、7；
可以看到退化成了一个链表的形式。
当我们查询7的话，时间复杂度就变成了单链表一样了。
从大到小也是： 
总结如下：
- 如果数据库底层使用二叉搜索树的话，遇到数据为极端的情况下会退化成单链表，所以不太合适；
可以想象一下，如果我们给自增的一列使用二叉搜索树的索引数据结构的话，是不是就很倒霉了。这就是极端的情况，都在一边。
(二)为什么红黑树不适合数据库索引？
红黑树又叫：二叉平衡树
红黑树作为Java开发人员应该很耳熟吧，JDK8中的HashMap中的底层数据结构就用到了红黑树。
这么牛逼的JDK中都用到了红黑树，为什么数据库中的索引数据结构不太适合呢？
还是上面那个假设，假设我们给Col1加上红黑树的索引。
过程如下动态演示： 
如果我们执行：
select * from table1 where Col1 = 7;
动态演示如下：
可以看到，我们一共查询了4次就查到了。与没加这个索引之前还是有比较大的效果的，至少没有全部扫描。
总结：
通过观察可以看到，每次插入几乎都会去调整这颗二叉树，保持高度是平衡的。 如果数据量非常大的话，也是非常耗时的，所以红黑树也是不太合适。
(三)聚集索引和非聚集索引
回答这个问题之前先来看一下Mysql底层数据文件的存储方式，这里拿MyISAM和InnoDB两种引擎来做比较。
1、MyISAM引擎
如上图所示，MyISAM引擎的表，在硬盘上存储着3种文件格式，分别是“.frm”、“.MYD”、“.MYI”;
- “.frm”：整个数据表的框架，也就表的结构。
- “.MYD”：D是data的意思，这个文件是存储的数据。
- “.MYI”：I是Index的意思，这个文件是存储的索引。
可以看到表的结构、数据、索引三种都分开来。这个就是非聚集的。
2、InnoDB引擎
与MyISAM引擎不同的是，InnoDB引擎在硬盘上只存储来2种文件，分别为：“.frm”、“.ibd”；
- “.frm”：表的结构/框架；
- “.ibd”：此文件存储着表的索引和数据；
可以看出InnoDB引擎把数据和索引同时存储在来一个文件里，这就是聚集索引。
二、MySQL中索引的实现（摘）
在MySQL中，索引是在存储引擎层实现的，不同存储引擎对索引的实现方式是不同的，下面我们探讨一下MyISAM和InnoDB两个存储引擎的索引实现方式。
（一）MyISAM索引实现：
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，MyISAM索引的原理图如下。
这里假设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。
可以看出MyISAM的索引文件仅仅保存数据记录的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示。同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。 
（二）InnoDB索引实现：
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件。
从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
下图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。 
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。下图为定义在Col3上的一个辅助索引。这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。 
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
