MYSQL索引

MYSQL索引机制

MySQL的索引机制,是提升数据库查找效率的十分重要的组件,而且对于SQL的优化也是相辅相成的,并且基本上面试问到数据库,一定会问索引这一块,所以很有必要整理一波。

什么是索引?

索引其实是一种检索机制,可以把他理解为是一种目录,就像我们查字典,如果我们需要查某个字,或者某个单词,一定是通过目录去找,肯定不会从第一页开始遍历吧。这样是不是大大提高了查询效率呢?数据记录数量越大,效果越明显。

那么MYSQL是如何实现索引的呢?

这里我们要提出一个页的概念,我们使用数据库存储数据的时候,都是将数据存到磁盘当中去的(当然这要根据数据库的使用引擎决定,Innodb和MYSIAM是存到存到磁盘,但是Memory是存到内存中的),但是我们从磁盘中读取数据的效率太慢了,和从内存中读取数据的速率根本不是一个数量级,那么页就相当于是存在内存和磁盘中间的介质了。
MYSQL中的页的单位是16kb,也就是16384个字节,页当中存储了很多信息,我们先只讨论其中的行数据
这就意味着,当我们要存储很多行数据的时候,就会开辟很多个页去存放信息,所以在每一页中,还会存放指向其他页的指针。
图片和部分内容来源此处

这里有个行溢出的问题: 就是当我们存取的一行数据刚好超过第16kb的时候,这时候就必须再开辟一页去存放这一行的数据,这就是行溢出。
如何解决呢?这里会涉及到行格式的问题,有些行格式,当一页存不了一行的时候,会给这一行多加一个指向某一页的指针,去继续在其他的页存储数据;不过也有的会既然存不下,就不存了,指向某一页,让他去存储。
不过也可能说,你的一行就超过16kb,那你就得好好思考如何简化了,1kb其实就能存放很多的字符了。

回到正题,那么我们的数据库是如何实现索引的呢?那么为什么索引能提高查询效率呢?
我们建立数据库索引,其实就是为数据库建立了一个目录,而这个目录的数据结构就是我们的B+树(B+Tree)。

常用的索引有:B+树索引,哈希索引,和全文索引

问题又来了,什么是B+树,为什么他能提高查找效率呢?
通俗来讲:
B+树,是一颗自平衡的查找树,他的每一个节点能够存放多个数据,并且每个数据从左到右,都是依次有序的,每个非叶子节点也是有序的,每个叶子节点也是有序的。
他不像AVL树,只有左孩子有孩子,不想B-Tree,每个节点是限制了的,
这就意味着我们的B+树,比其他的树更加的胖,也就是高度更低,查找的次数就越少,我们来看一看,当我们建立索引之后是如何查找数据的:
我们可以看出来,我们的每一页就是B+树中的每个节点,但是注意的是这里我们只在根节点去存储数据和主键(这也是我们的主键索引)

主键索引又叫聚集索引,就是建立在主键上的索引,他的特点是我们的叶子节点会存储主键和数据,这样我们通过主键索引能直接找到对应的这条记录;
非聚集索引就是索引不是主键的索引,他的叶子节点上存放的是索引列以及主键,这就意味着,当你需要通过索引找到非索引列的数据时,需要再次通过主键,去查找对应的记录

这里我们只进行了三次IO遍找到了对应的记录,
如果你没有建立索引,你得遍历页,再遍历页中的记录,在庞大的数据背景下,尤为吃力。
如果我们的数据量是百万,千万级的呢,他还能这样吗?

我们可以计算一下,一页16kb假设我们每一行存储1kb,非叶子节点存放的时索引列和指针也就是8+6=14个字节,当我们有两层的B+树的时候我们能存储的树为16384/14*16约为1.8w条记录
当我们是三层的时候,就再乘以16384/14,可以存放2kw条数据,相当多了

那么我们使用B+树索引有什么好处呢?

这里我们在说说另外一个常见的存储结构,那就是哈希索引
他类似于散列表,把数据根据特定的算法,储存在表中的某个位置,利用这个算法的查找效率相当高,但是他有几个重要的缺陷:

1. 不能够排序,不能够排序,为我们之后的优化又可能添加麻烦
2. 不能够支持范围查找: 他存在表中的数据是无序的,意味着,他是无法进行范围查询的,不像B+树,已经是自动排序了的
3. 当我们的数据存在大量重复的时候,他会产生哈希碰撞(想想哈希表),这样他的效率将大大降低
4. 不支持最左前缀原则

什么是最左前缀原则?

这里特指的是联合索引,也就是多条列联合建立的索引。但是如果使用不当,会造成索引失效。
当我们建立联合索引(a,b,c,d)的时候,我们必须保证最左边的值一定是给等值,也就是说我们的a这一列的查找条件必须是明确的,有序的:
比如where a=1;或者a>1 and a<5;这样查找的数据都是明确的有序的,后面的条件才能够继续使用索引去查找
但是如果是where a like %2%;是无法命中索引的,直接退化成线性查找,
但是like 1%是可以命中的
而且where a=1 and b=2 and c>5 and d=6,a,b,c会命中索引,但是d不会,这就是因为当遇到c是个范围时,你无法保证后面的数据是有序的,这就使得后面的列无法命中索引。
这就好比,让你用字典查单词 第一个单词为a,第二个为b,第三个比c大,第四个为d,你能通过索引去成功定位d这个单词吗,显然不能.
这里要注意的是,是否符合最左前缀原则,不是看你查询条件的最左边,而是你建立索引列的最左边。
当然你可以使用explain关键字,去查看你操作的时候数据库到底是怎样分析的:

possible_keys就是可能用到的索引,key就是真正用到的的索引。