mysql之索引详解

mysql索引

一、存储引擎

mysql存储引擎有以下几种类型：myisam、innodb、csv、memory等，当然常用的还是myisam和innodb

myisam和innodb的区别

所以 MySQL5.5版本开始Innodb已经成为Mysql的默认引擎(之前是MyISAM)，说明其优势是有目共睹的。如果你不知道用什么存储引擎，那就用InnoDB，至少不会差

二、物理位置

在物理存储上，一个数据库对应一个文件夹

数据库文件存储的位置:my.ini配置文件中,datadir对应的数据目录位置

myisam每个表对应三个文件

*.MYI:存放的是数据表对应的索引信息和索引内容;

*.FRM:存放的是数据表的结构信息;

*.MYD:存放的是数据表的内容;

InnoDB每一张表对应一个文件

*.frm 存放的是数据表的的结构信息

*数据内容和索引文件都是统一存放在ibdata文件中.

所以索引文件都是额外进行存放的,对应索引的查询以及维护都是需要消耗IO的;

三、索引类型

普通索引

最基本的索引，没有任何使用限制

唯一索引

与前面的普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一

主键索引

是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。一般是在建表的时候同时创建主键索引

组合索引

指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用组合索引时遵循最左前缀集合

全文索引

一般使用在全文搜索上，主要用来查找文本中的关键字，而不是直接与索引中的值相比较。fulltext索引跟其它索引大不相同，它更像是一个搜索引擎，而不是简单的where语句的参数匹配。

四、索引注意事项

1.索引不包含null值的列，所以我们在数据库设计时不要让字段默认值为null

2.短索引，如果一个字段char（255）的列表，前15个字段多数值是唯一的，就不要对列进行索引。短索引可以提高查询速度和节省I/O操作

3.索引列排序，查询只使用一个索引，因此如果where子句中已经使用了索引的话，那么order by中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作；尽量不要包含多个列的排序，如果需要最好给这些列创建复合索引。

4.like语句，一般情况下不推荐使用like操作，如果非使用不可，如何使用也是一个问题。like “%aaa%” 不会使用索引而like “aaa%”可以使用索引。

5.不要在列上进行运算，这将导致索引失效而进行全表扫描，例如

SELECT * FROM table_name WHERE YEAR(column_name)<2017;

6.不使用not in和<>操作

五、索引底层结构

1.查询算法

索引的作用是做数据的快速检索，而快速检索的实现的本质是数据结构。通过不同数据结构的选择，实现各种数据快速检索。在数据库中，高效的查找算法是非常重要的，因为数据库中存储了大量数据，一个高效的索引能节省巨大的时间

2.哈希表

哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的 key 地址，通过这个地址进行具体数据的数据结构

假设我们要取出id=7的数据，哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存储的数据的物理地址，通过该独立地址可以找到对应 user_name='g'这个数据。这就是哈希算法快速检索数据的计算过程

拓展：数据碰撞问题？时间复杂度 O（1） ？范围怎么查询？

3.二叉树

二叉查找树的时间复杂度是 O(lgn)，比如针对下面这个二叉树结构，我们需要计算比较 3 次就可以检索到 id=7 的数据，相对于直接遍历查询省了一半的时间，从检索效率上看来是能做到高速检索的。此外二叉树的结构也能解决哈希索引不能提供的范围查找功能

但是我们需要思考在数据库中，数据的自增是一个很常见的形式，比如一个表的主键是 id，而主键一般默认都是自增的，如果采取二叉树这种数据结构作为索引，那下面的极端的图是不是必然出现，然后时间复杂度是否变成了N？

4.红黑树

针对二叉树的极端情况， 我们可以让树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态

红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态（时间复杂度为 O（logn）），也就保证了查找效率不会明显减低。比如从 1 到 7 升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态，如下图所示。下面这个红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率。

5. AVL 树

AVL树其实就是不断调整，最终绝对平衡。 也正是因为 AVL 树是个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能会更多。

目前可以满足查询需求了，不错的查找性能（O（logn）），不存在极端的低效查找的情况。可以实现范围查找、数据排序。

但是

数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

6.B树

下面这个 B 树，每个节点限制最多存储两个 key，一个节点如果超过两个 key 就会自动分裂。比如下面这个存储了 7 个数据 B 树，只需要查询两个节点就可以知道 id=7 这数据的具体位置，也就是两次磁盘 IO 就可以查询到指定数据，优于 AVL 树。

但是考虑到磁盘 IO 读一个数据和读 100 个数据消耗的时间基本一致，那我们的优化思路就可以改为：尽可能在一次磁盘 IO 中多读一点数据到内存。这个直接反映到树的结构就是，每个节点能存储的 key 可以适当增加。

7.B+树

B 树和 B+树有什么不同呢？

第一，B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。

第二，B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

通过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。