共计 2433 个字符，预计需要花费 7 分钟才能阅读完成。
前言
在日常工作中，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 会以主键形成一颗索引树存储数据记录，反过来讲：数据的存储依赖于主键索引。那么，如果咱们不设置主键会产生什么？
- 首先，MySQL 会找表中是否有惟一索引，如果有，就以惟一索引作为主键。
- 如果没有惟一索引，那么将增加暗藏字段 rowid 作为主键。
查找算法
以下图索引树为例，查找 id=30 的行记录的过程是怎么的呢？
图中空白局部存储的为下个结点的磁盘地址，如根结点 [15-56] 之间的空白点存储的就是指向最右边子结点的磁盘地址。
1、首先，将根结点加载到内存中(后续根结点常驻内存)
2、二分查找 id=30 的地位，定位在 15-56 之间，读取下一个结点的磁盘地址
3、加载结点到内存，持续二分查找，定位在 20-49 之间，读取磁盘地址
4、加载叶子结点，找到 id 为 30 的记录
5、如果是通过二级索引查找，则持续应用主键回表查找主键索引
追更，想要理解更多精彩内容，欢送关注公众号：程序员阿紫
集体博客网站：https://zijiancode.cn
