mysql之索引详解

原创
04/07 16:17
阅读数 115

mysql索引

一、存储引擎

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

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+树在查找效率、范围查找中都有着非常不错的性能。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部