1.深入理解MySQL索引底层数据结构与算法

索引的概念

索引是帮助MySQL高效获取数据的排好序的数据结构

数据结构

网址： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉树

如果底层使用二叉树的话，比如顺序插入：1,2,3,4,5,6,7
那么数据结构就会变成一下这样

由动画可见，变成一个链表，这时候要查询6，就会经过6次查询才能找到，这个时候和全表扫描没什么区别。效率没什么提升。

红黑树

那么为什么不使用红黑树呢，当然使用红黑树也会出现问题,如果按照以上数据插入的时候，动画如下：

这时候如果要查询6的话，只需要经过三次查询，分别是2,4,6经过三次查询，和二叉树相比少了一半的查找时间，
那么为什么没有使用红黑树呢？

• 树的高度：现在是有7条数据假设数据量是几百万行呢，所以红黑树也不是最好的选择。
• 自旋：每次插入数据都是进行判断，是否符合红黑树规则，若不符合进行自旋，如果频繁插入就会导致频繁，浪费性能。

B-

让存储空间稍微大一点，可以放更多的数据元素(第一行数据)，一个大的节点下放很多小的索引元素，data可能是索引所在行的磁盘空间，一个小的节点就是一个KV。
对比红黑树又有了提升，其实底层也不是完全使用了B-树，而是自己在B-树上进行了改造，使用了B+树。

B+

和B-树对比，将data放在了叶子节点上，那么这么做有什么好处呢：
首先是非叶子节点的大小，可以存放更多的索引数据
其次叶子节点包含了整表的数据元素。

非叶子节点是什么东西呢？
其实就是冗余索引，为了构建B+树。
每个节点都是排好序的，从左到右，依次递增，其实B-也是具有的。

两者的区别

1. 指针的区别：就是B+树是存在左右箭头⬅️➡️指针的，存在下个节点的所在位置，可以快速查找。

2. 数据量大小：

   • B+树 ： 假设用Bitint做主键，每个索引占用8个字节(8B),下个文件的所在文件地址在C语言底层大概占用6B,MySQL索引大小默认是16KB，可以放置1170个元素，第二层又可以放置1170个元素，叶子节点有个date元素，可能是文件的所在地址，也可能是数据本身，这个数据就比较大，假设为1KB，那么总数据量为 1170117016 = 21902400个元素
   • B-树，假设也是三层按照以上逻辑计算为161616 = 4096个元素

   真正运行中MySQL可能会把根节点常驻内存中，这样效率得到进一步提升。

Hash

Hash的数据结构是将值进行hash之后放进哈希桶之中，比如Alice进行Hash之后是2放在2的后面，Jim进行Hash之后还是2通过链表的形式放在了Alice的后面，Tom通过hash之后得到4，放在4的后面。

如果要查询Tom可以直接进行Hash,得到4，从而直接得到数据，这种时候获取数据的形式比B+树要更高效。
但是有个弊端，就是没办法进行范围查询。

引擎

数据所在位置

对应关系

两种引擎的区别是什么呢

MyISAM

由上图可见，MyISAM引擎的数据和索引是分开来的(account)

• frm为数据表结构相关的信息
• MyD 数据
• MyI 索引

底层文件分为

InnoDB

由上图可见，MyISAM引擎的数据和索引是分开来的(test_myisam)

• frm为数据表结构相关的信息
• idb为数据和索引

底层文件分为：

索引

主键

为什么必须包含主键？
能够唯一区分表中的每一行数据。 如果没有主键的话，更新或者删除表中的特定行就会很困难。如果没有设置主键，数据库本身就会自己帮忙维护一个虚拟主键。

为什么推荐整形自增？
首先索引是一个排好序的数据结构，其次数据库的资源性能都是比较宝贵和昂贵的，让数据库自己去排序，显而有点浪费资源。

聚集索引

由于InnoDB底层文件图片可知聚集索引的叶子节点存的是数据，找到之后可以直接把数据取出来。不涉及到回表的操作，在性能上高于非聚集索引。

非聚集索引

为什么建立二级索引？假设一张表的数据比较多，我多建几个索引很正常吧！

由于InnoDB底层文件图片可知聚集索引的叶子节点存的是一级索引的key，这个时候设计到一个回表查询的一个操作。

这也是为什么引擎逐渐改为了InnoDB引擎的原因，MyISAM通过索引查询数据涉及到了跨文件查询。

为什么非聚集索引存的是聚集索引的key(主键值)

• 第一是为了节省空间，假设也是存数据到话，data可能会很大，占用太多的资源空间
• 第二是为了保证一致性，假设要插入一条数据，主键写入成功后，二级索引也要写入成功算是成功，如果写入主键值会快很多并且出错率更低。

联合索引

遵循最左前缀原则，那么为什么要遵循最左原则呢？
假设一：遵循最左原则：查询name 和 age
条件为：Bill和30
可以得到第一条数据

假设二：不遵循最左原则：查询age和position
条件为:30和dev

查询到了第一条数据，这个时候后面还有符合的数据就需要重新回表查询

因为索引是排好序的数据结构

如有写的不对的请指正。