MySQL - 索引的数据结构
目录
一、为什么使用索引
二、索引及其优缺点
1.索引概述
2.优点
3.缺点
三、InnoDB中索引的推演
1.索引之前的查找
在单页中查找
在多页中查找
2.设计索引
3.常见索引概念
4.InnoDB+树索引的注意项
四、MyISAM中的索引方案
1.MyISAM索引的原理
2.MyISAM与InnoDB对比
五、索引的代价
六、MySQL数据结构选择的合理性
1.全表遍历
2.Hash结构
3.二叉搜索树
4.AVL树
5.B-Tree
6.B+Tree
7.R树
零、算法的时间复杂度
一、为什么使用索引
索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本教课书的目录部分，通过目录找到对应文章的页码，便可快速定位到需要的文章（当你把本篇全部看完这之后会发现，这个比喻可能不太合适，前提是看完...）。MySQL中也是一样的道理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条-条地查找记录, 直到找到与条件符合的记录。
如上图所示，数据库没有索引的情况下，数据分布在硬盘不同的位置上面，读取数据时，机械臂需要前后移动查找数据，这样操作非常消耗时间。如果数据按序摆放，那么也需要从1到6行按顺序读取,这样就相当于进行了6次I/O操作，依旧非常耗时。如果我们不借助任何索引结构帮助我们快速定位数据的话，我们查找Col2= 89这条记录，就要逐行去查找、去比较。从Col2=34开始,进行比较，发现不是，继续下一行。我们当前的表只有不到10行数据，但如果表很大的话，有上千万条数据，就意味着要做很多很多次磁盘I/O才能找到。现在要查找Col2=89这条记录。CPU必须先去磁盘查找这条记录，找到之后加载到内存，再对数据进行处理。这个过程最耗时间的就是磁盘I/O (涉及到磁盘的旋转时间(速度较快)、磁头的寻道时间(速度慢、 费时))。
加入数据使用二叉搜索树结构来进行存储，如下图：
可以看到每一个节点下方都会存在两个子节点。二叉搜索树其规律在于，比自身小的数全部放在了左子节点，比自身大的数都放在了右子节点。其每一个节点都是KV键值对结构。比如说这次还是要找到数字89，从最上面的34开始对比，因为89>34，所以直接把其下方的所有左节点全部省略，直接去右边进行查找，这样的话效率会高很多。
这就是我们为什么要建索引，目的就是为了减少磁盘I/O的次数，加快查询速率。
二、索引及其优缺点
1.索引概述
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查找算法 。
索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。
2.优点
（1）类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的I/O成本，这也是创建索引最主 要的原因。
（2）通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
（3）在实现数据的 参考完整性方面，可以加速表和表之间的连接。对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
（4）在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低了CPU的消耗。
3.缺点
增加索引也有许多不利的方面，主要表现在如下几个方面：
（1）创建索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间也会增加。
（2）索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
（3）虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。因此，选择使用索引时，需要综合考虑索引的优点和缺点。
提示:
索引可以提高查询的速度，但是会影响插入记录的速度。这种情况下，最好的办法是先删除表中的索引，然后插入数据，插入完成后再创建索引索引。
三、InnoDB中索引的推演
1.索引之前的查找
一个精确匹配的栗子：
SELECT [列名] FROM [表名] WHERE [列名] = xxx;其效果如下：
数据在底层存储时的基本单位叫做数据页，一个数据页的默认大小为16Kb。 所以说一页的存储量是有限的，在日常操作时会经常的使用到多个数据页。
在单页中查找
假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同，分为两种情况：
- 以主键为搜索条件
主键在多数情况下为自增特性，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
- 以其他列作为搜索条件
因为在数据页中并没有对非主键列建立所谓的页目录，也不一定存在自增的特性，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录（第一条记录）开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
单链表： 在一个数据页中存储这一条一条的记录。这些记录在底层的物理磁盘上是不可能一次排列的，它们一定是被打散然后存储在物理磁盘上的。 （因为要将大量的数据依次排列在物理磁盘上是很"崩溃"的一件事，每一条记录都要往后移，效率是非常差的） 所以我们只需要保证它们在逻辑上存在连续性即可。也就是使用"单链表"来进行连接。 也就是说每一行之间，都是用单链表来进行连接的。 这里提一嘴，每一行都一个"行格式"。
在多页中查找
大部分情况下我们表中存放的记录都是非常多的，需要大量的数据页来存储这些记录。在多页中查找记录的可以分为两个步骤：
1.先定位到记录所在的页。
怎么定位到页呢？ 比如我们要查找的数据没有任何的自增等特性，又分布在大量的页当中。那就只能对每一个页进行一一遍历，那么效率其实是非常低下的。 当然你也可以将所有的页全部加载到内存中去，当然加载的过程也是及其消耗时间的，甚至会远高于你去遍历所有页的时间。 所以咱们就考虑到要去使用索引。
2.再从所在的页内中查找相应的记录（再重复上面的步骤以主键为搜索条件或以其他列作为搜索条件）。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然超级耗时。此时索引应运而生。
2.设计索引
先来创建一个表，记得先进一个数据库：
CREATE TABLE index_demo(
c1 INT,
c2 INT,
c3 CHAR(1),
PRIMARY KEY(c1)
) ROW_FORMAT = Compact;
这个新建的 index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键， 这个表使用 Compact 行格式来实际存储记录的。这里我们简化了 index_demo 表的行格式示意图：
