61 mysql索引底层实现

Mysql性能优化原理

1.MySQL索引数据结构类型有那些？
hash B+树
2.Hash索引、二叉树、平衡二叉树/红黑树、B+树之间的区别
3.索引如何支持千万级表结构的快速查询？
4.为什么最终MySQL索引选择B+树？
1，支持范围查询
2， 降低树的高度，减少磁盘io的次数。

5.MyISAM与InnoDb引擎B+树索引底层原理
6.缓存页与B+数索引之间的关系

1，索引如何支持千万级表结构的快速查询？
假设使用B+树存放元素，做一次磁盘io的操作 查询16kb 假设主键整数类型为8个字节，指针大小占用6个字节
每个节点存放索引102416/14=1170个索引元素 11701170=1368900*16 20000000左右，树的高度为3.

mysql 服务器读取硬盘数据是以页为单位 16kb 读取硬盘中数据到缓存区内存中。
数据存放在硬盘中： 硬盘io操作。
如何减少磁盘io操作。

Mysql 索引底层实现原理：
Mysql官方定义索引： 索引(index)是帮助Mysql高效获取数据的数据结构类似于书的目录结构一样。

mysql索引结构： hash索引， 二叉树，平面二叉树/红黑树 b树 B+树。

1 使用hash索引类似于 hashmap key 计算index
优点： 等值查询的时候效率非常高
缺点： hash算法 数据存放散列 不支持范围查询。
2，使用二叉树

特性： 左子树和右子树 根节点
左子树根节点值要小
右子树根节点值要大。
缺点： 斜树 形成链表的结构。

为什么二叉树 形成链表： 如果首节点值比较小的情况下，在做自增的时候形成链表不平衡。

3 平衡二叉树 avl/红黑树：
他是一颗空树或他的左右2个子树的高度差的绝对值不超过1
使用旋转+变色 保证左右2个子节点的高度差不超过1

缺点： 随着数据量增多，树的高度越来越高，做磁盘io操作次数越多，效率非常低。
原因
MySQL数据库结构模拟图
https://www.cs.usfca.edu/~galles/visualization/BST.html
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

4，B树， 缺点： 数据冗余 叶子节点存放索引和data 数据
叶子节点存放索引和data数据，每个节点缓存索引不会太多。

5 b+树 mysql 索引底层实现原理
分成叶子节点和非叶子节点
叶子节点存放在索引和data数据
非叶子节点不存放data数据，只存放索引。
索引和data数据分开
按照页读取范围更大
索引如何支持千万级查询？
1，mysql 底层使用 页为单位读取16kb
2，做第一次磁盘io操作的时候 读取16kb 的索引内容
3，一个索引值bigint类型8个字节 ，指针6个字节 14个字节。
4 161024/14=1170 个索引， 11701170=1368900
5, 分析 b+树高度为3的情况 假设叶子节点 每一行数据1kb。
1368900*16=2000万

image.png

MyISAM与 Innodb 如何使用b+ 树
MyISAM
1 MyISAM基于b+树实现，索引的文件和物理数据分开。
2 MyISAM 底层基于 叶子 data数据 通过指针指向 myd数据文件对应行
Innodb:
1,Innodb 索引的文件和物理数据没有分开
2，Innodb叶子节点data数据存放对应行数据。
3 Innodb 非主键索引叶子节点data 主键id ，需要查询2次
先查询非主键索引的文件，得到主键id，在根据主键id查询主键索引的结构。
得到整行的数据。

存储引擎和表有关系。
为什么 Innodb 引擎表必须有主键 并且推荐使用整型的自增方式？
1，主键id 不要使用UUID、 不支持范围查询
2， 无法实现比较 其次比较占用内存。
3，建议主键id采用整数类型自增。