前言

在日常工作中,MySQL无外乎是咱们最相熟的数据库了,了解MySQL的数据结构和索引特点,可能帮忙咱们写出查问效率更高,逻辑更为明确的SQL,也能给咱们设计表构造时带来思路。

数据结构

索引

对于MySQL的优化咱们第一想到的总是索引,那么,什么是索引呢?

索引是一种帮忙MySQL高效获取数据的排好序的数据结构,如果是你,你会选用什么样的数据结构作为MySQL的底层存储?

如何抉择数据结构

基于咱们日常应用MySQl的状况,能够大抵总结一下此数据结构的特点

  • 查问效率高
  • 反对数据量大,在千万级以上数据量时也要放弃查问的稳定性
  • 对范畴查问敌对

首先第一点:查问效率高,在泛滥的数据结构中,查问效率最高的必须是树了。

而反对查问的树有:

  • 二叉搜寻树
  • 红黑树
  • B树
  • B+树

二叉搜寻树

先不管它是否反对其余点,咱们晓得,平时咱们的插入数据都是主键都是自增有序的,当二叉搜寻树遇到这状况会产生什么?

此时,二叉搜寻树进化成了链表。所以,该构造被咱们pass掉了。

红黑树

简略来说红黑树是颗均衡树,当遇到某一边过长时将进行均衡,就像这样

所以它解决了进化为链表的问题,然而当数据量过大时,比方数据量达到1千万,他的树高为 2^n = 1千万,n大略是24。

也就是查问数据时,可能会有0~24次IO,时快时慢,所以这个数据结构,也不行。

B树

由上可知,树的高度决定了IO的次数,也就是查问效率。那么,该如何缩小高度?

以上的树结构每个结点都只存了一个元素,如果咱们能让一个结点存多个元素,是不是就能显著升高层高了?

这就是B树了

插入过程如图

和二叉树比照,树的高度的确会减小,每一个结点可能寄存的元素越多,树的高度就减小的越多。

但它仍旧有些别的毛病:

  • 范畴查问,显然,这棵树对范畴查问的确不敌对,比方从3到7,还是得一次一次的查出来。
  • 在MySQL中,每行记录可不是只有1,2,3这种数字,还有很多其余的数据,一个结点的空间是无限的,每行记录越大,一个结点能寄存的元素(记录)就越少,数据结构相似这样

针对于以上两个问题,咱们来看看B+树又是怎么解决的?

B+Tree

先来看看B+Tree的构造

B+tree相比于B-tree,有三个不同点:

  • 叶子结点有相互指向的指针,便于进行范畴查问,比方3-7,首先定位到3,而后从左往右遍历即可
  • 叶子结点寄存所有数据,其余非叶子节点冗余叶子结点的地位(用于定位),比方图中的4
  • 非叶子结点不存放数据,只寄存索引,如此一个结点就寄存更多的元素,就像这样

在MySQL中,一个结点的默认大小为16kb,指向其余结点的指针为6b,假如咱们以主键(long类型)为索引,那么主键占用的空间为8b

如此,一个非叶子结点能够寄存的元素个数为:16kb/(6b+8b)=1170

假如每行记录的大小为1kb,则一个叶子结点能够放16kb/1kb=16行记录

假如一颗3层的B+树,那么能够存放数据的行数为1170 1170 16 = 2.2千万

每行记录越小,则能够存放数据的行数越大,假如一行数据只有512b,则3层B+树能够寄存4.4千万数据,这也是为什么垂直分表可能进步查问效率的起因之一。

综合以上状况,千万级数据量的表,查问数据也最多只有经验3次IO,而且根节点其实常驻在MySQL内存中。

Hash

Hash也是MySQL中的一种数据结构

它的特点如下:

  • 对索引的key进行一次hash计算就能够定位出数据
  • 存储的地位仅能满足 “=”,“IN”
  • 不反对范畴查问Hash抵触

存储引擎

在日常工作中,罕用的存储引擎有两种,InnodDB和MyISAM

InnoDB

汇集索引:叶子结点存储残缺的数据,主键索引即数据文件

磁盘上以两个文件存储表信息

  • table.frm: 表构造文件
  • table.idb: 索引数据文件
比非汇集索引效率更高:缩小了一次回表

MyISAM

非汇集索引:叶子结点存储的是指向数据的磁盘地址,索引和数据拆散。

磁盘上以三个文件存储表信息

  • table.frm: 表构造文件息
  • table.MYI: 索引文件
  • tbale.MYD: 数据文件

二级索引

在开发时,咱们不仅会通过主键查问数据,也会通过其余字段查问数据,如username,此时也应该给username字段建设索引。

此类除主键索引之外的索引,称为二级索引或者辅助索引。

二级索引同样是颗B+树,与主键索引不同的是:二级索引的叶子节点并非存储残缺的数据,而是存储主键。

为什么二级索引存储的是主键而非残缺数据?

  • 一致性:如果二级索引也存储残缺的数据,那么批改数据后就会很麻烦,须要批改主键索引又要批改二级索引。
  • 节俭磁盘空间

二级索引又分为一般索引和惟一索引。一般索引中比拟特地的是联结索引,这也是平时开发打交道最多的索引。

联结索引

联结索引指由多个字段组成的索引,如name+age+positon形成这样一颗索引树,索引同样是从小到大排列,先排序第一个字段,第一个字段雷同时排序第二个字段,以此类推。

基本上,大部分的索引优化准则都是基于联结索引

建表时如果不设置主键会怎么?

下面说到,MySQL会以主键形成一颗索引树存储数据记录,反过来讲:数据的存储依赖于主键索引。那么,如果咱们不设置主键会产生什么?

  1. 首先,MySQL会找表中是否有惟一索引,如果有,就以惟一索引作为主键。
  2. 如果没有惟一索引,那么将增加暗藏字段rowid作为主键。

查找算法

以下图索引树为例,查找id=30的行记录的过程是怎么的呢?

图中空白局部存储的为下个结点的磁盘地址,如根结点[15-56]之间的空白点存储的就是指向最右边子结点的磁盘地址。

1、首先,将根结点加载到内存中(后续根结点常驻内存)

2、二分查找id=30的地位,定位在15-56之间,读取下一个结点的磁盘地址

3、加载结点到内存,持续二分查找,定位在20-49之间,读取磁盘地址

4、加载叶子结点,找到id为30的记录

5、如果是通过二级索引查找,则持续应用主键回表查找主键索引


追更,想要理解更多精彩内容,欢送关注公众号:程序员阿紫

集体博客网站:https://zijiancode.cn