MySQL|MySQL为什么选择B+树存储索引 mysql|性能优化|b树

MySQL为什么选择B+树存储索引

为什么加索引?
MySQL的索引是什么
索引存储方式
数据使用索引的存储方式
- 二叉树
- B树
- hash表存储方式
联合索引

为什么加索引?

文章图片

如果上面的表,我们执行SQL语句

select * from table where Col2=89;

这样就会造成全表扫描，从第一行读取到倒数第二行，然后拿到这个89这个对应的值的位置，这样就做了6次才找到对应的值，但是加上索引就不一样了，接下来介绍索引是什么?
MySQL的索引是什么索引是帮助MySQL高效获取数据的排好序的数据结构
索引的数据结构包括：

二叉树
红黑树
Hash表
B-Tree

索引存储方式索引存储是按照KV方式进行存储的，key是这个索引元素，比如34，77等，value是这个索引在磁盘上面的文件地址，索引也是落地到磁盘上面的，因为数据是落在磁盘上面的，然后根据这个key对应的value去磁盘上面找到对应的值，然后输出。
数据使用索引的存储方式二叉树

文章图片

这样是不是就很快了
但是二叉树这个数据结构在某些情况下并没有什么效果，比如这个col1这一列，他是1-6的连续数据。
他的二叉树结构就是如下

文章图片

虽然还是二叉树，但是这个和没有索引效果是一样的
所以MySQL最终选的不是二叉树
然后第一种二叉树排除了
然后对比一下红黑树
jdk1.8之后hashmap之前就是数组加链表存储的，假如链表非常长的时候，在hashmap里面查找元素性能也不是很好的快速查找所以在jdk1.8之后，在hashmap的底层链表被优化成红黑树，查找性能优化很高
红黑树的索引要是将1-7变成如下

文章图片

红黑树也是二叉树，也叫做自平衡二叉树，二叉平衡树
但是MySQL最后之所以没有选择红黑树，因为红黑树在某些场景下并不能满足需求，因为用红黑树存储索引在某些情况下有如下问题：

层级太多，因为我们只有7个数据，层数即高度就这么多，如果要是很多的数据，那样不就更多了，假如树的高度是20，我们查找的元素在叶子结点,最快最快也要经过20次查找，也就要经过20次磁盘io查找。
MySQL是将这个数据结构存储在磁盘上面的，假如你先存储了10个数据，然后过了几天又存储了10个数据，中间间隔了很多天，因为数据都是要写到磁道上面，这段时间间隔可能写了很多其他数据，可能都跨磁道了，这样查询起来更慢了，因为他也是都磁盘上面找的。

树的高度越低，查找速度越快，最好对这个树的高度做一下优化，即使上千万数据，也让这个树的高度小于4，这个是可能的。
因为我们比如插入一条数据，他是先在磁盘上面开辟一个空间，然后再将数据存储上去，我们就可以一次开辟多个空间，这一行存储多个节点，然后这个多个节点又能分出很多只。

文章图片

上图就得到了一个B树的结构,
所以就引出了B树，B树就是B-树，两个是一个东西
B树他就是上面二叉树的变种，只不过每一个节点存储了多了key和value，而不是之前的一个
MySQL底层实际上用的是B树的变种，叫B+树

文章图片

B+树他的叶子节点才会存储这个data，这个data对应的是这个数值在磁盘上面存储的位置，即我们最上面说的那个value
B+树每一个节点从左往右是依次递增的，而且15、18是在15-20之间，叶子结点之间用指针链接。
子节点大于等于他左边的父节点，小于右边的父节点
所有叶子结点也是从左往右依次递增，MySQL维护时候也是方便维护的
B+树也叫多路(叉)二叉树，底层也是二叉树
MySQL在B+树下如何查询：
查找30为例

首先将最上面的这个如15、56、77加载到内存，这是一次磁盘的IO操作，然后在内存查找
然后发现30是位于15、56之间，然后去他们两个之间的那个空白节点把下面第二行的地址拿到，然后将这个对应的第二行加载到内存，又是一次磁盘IO操作
然后发现这个30位于20和49之间，然后读这个第二行的20和49之间的地址，将对应的第三行读取到内存，第三次磁盘IO。

疑问：为什么不把所有数据都放在第一行呢？
答：假如数据量很大，几千万行数据，一次把几千万行数据直接加载到内存，那样内存大概率感触几百兆。而且一次磁盘IO撑死几M，可能就几十K，几百兆的一次磁盘IO完成不了，磁盘IO几百兆也需要几秒钟或者几十秒。

所以这个每一行每一点存储多少K的数据，MySQL给我们提供了一个默认的，16K，这个一次磁盘IO读取16K数据还是很简单的，这个值是MYSQL研发人员在多次测试的成果下给设置的默认值，单位是byte

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

文章图片

为什么MYSQL默认设置为16K?
一般索引都是用INT或BIGINT
以bigint为例，比如这个索引15一般MySQL给他存储的是8B，然后他和56之间的空白格，这个是下一排的地址。是一个指针，索引和指针成对出现，这个一般是存储6B，MySQL给的值，所以一行16K*1024/(8+6)=1170个
叶子节点是没有这个空白区域，因为空白区域存放的是指针，叶子节点不需要指向下一位，所以没有这个指针，他的data占用的比较大，大概是1KB左右，所以叶子节点一个是存储16个元素

文章图片

假如一个三层的B+树放满了,就是1170117016≈两千两百万
所以就可能千万级别数据只需要查询三层
hash表存储方式 MySQL的索引也可以按照hash表存储方式

文章图片

MyISAM和InnoDB存储引擎：只支持BTREE索引，也就是说默认使用BTREE，不能够更换
但是hash索引某些存储引擎比如innodb是不支持的，除非经过特殊设置
hash表索引在MySQL用的很少
虽然用navicat在innodb和mylsam引擎下，可以选择hash索引，但是你会发现,点击保存，自动变成了BTREE，如果是memory引擎，他就可以选择hash索引，memory存储引擎支持hash索引存储和BTREE方式

文章图片

如果使用hash表存储的话，就是hash(索引值)，把这个hash索引值之后的结果和磁盘地址两个做一个唯一的映射，这样看起来好像感觉执行比如下面这个SQL好像比B+TREE更快，因为只需要对这个索引做一次hash，然后拿这个这个hash值去磁盘映射的位置找到这个对应的值即可
另外MySQL底层对hash碰撞(如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞)规避得很好

select * from a where Col1=1

但是，假如执行的是select * from a where Col2<89 and Col2>34，这个就是B+TREE更快了，绝大部分场景都是范围查找吧。所以MySQL默认是B+tree，但是也可以选择hashTree
用B+树查找时候，实现范围查找就非常快了，他的叶子节点之间用指针连接起来的，而且是双向的，首尾相连的