一、mysql索引

mysql索引是排好序的B+tree，所有节点在叶子节点，叶子节点为双向链表

1.1、mysql索引为什么不用二叉树、红黑树、B-tree树、哈希

  • 在数据量很大的时候二叉树特殊情况下会变成单向链表
  • 红黑树是二叉平衡树，数据量大的时候高度很高
  • 哈希时间复杂度虽然是0(1)，但是哈希无法支持范围查询，还有哈希冲突问题
  • B-tree树

image.png
a、所有节点分布在树上，并不是都在叶子节点 - 不利于范围查找
b、每个节点的索引和数据在一起 - 占用的空间多，树的高度变高。
c、叶子节点不互相关联 - 不利于范围查找

  • B+tree

image.png
a、非叶子节点不存储数据，只存储索引冗余，可以存放更多的索引
b、叶子节点包含所有节点数据
c、叶子节点用指针连接，提高区间访问的性能
d、叶子节点存放索引和数据 - 存放主键索引和数据，二级索引是单独的树，有时需要回表查询
注意：叶子节点为有序的双向链表
B树与B+树的区别

1.2、索引查找过程 - 折半查找

  • 先把根节点的所有数据load到内存
  • 因为是排好序的，所以直接利用折半查找法查找范围
  • 在将此范围下的第二层索引load到内存，以此类推

image.png

注意：mysql一页的数据是16kb，第一层的数据大小为1页（show global status like ‘Innodb page size’）, 假如主键为bigint类型，占用8个字节，白色区域（下一个节点的文件地址）占6个字节，16kb/14字节 = 1170个，第二层为 11701170，第三层叶子节点数据大小为1kb，相当于16个 11701170*16 = 2千万条多数据。B树未将数据放在叶子节点，那么每层存储的数据个数有限，那么树的高度会非常高
数据存储在叶子节点，是为了降低树的高度，当树的高度为3的时候，可存储2千万条数据，
如果不存储在叶子节点，每层可存储16条数据，则需要很多很多层，
mysql查询的速度取决于树的高度

1.3、联合索引

image.png
先按name排序，name相同按照age排序，age相同则按照position排序，所以查找遵循最左前缀法则，

二、存储引擎

  • 存储引擎是针对数据库表的
  • myisam有三个存储文件，表结构文件、索引文件、数据文件，采用非聚簇索引（索引数据分离）

— 先通过索引树找到对应索引，然后在根据索引去数据文件中查找数据
image.png

  • innodb有两个存储文件，表结构文件，索引文件和数据文件存储在一起，采用聚簇索引（索引数据在一起）

image.png

2.1、为什么innodb存储引擎要建主键并且建议主键递增

因为需要用主键构建B+tree索引树，如果没有主键会从表中挨个字段去找唯一索引，如果没找到则mysql会帮你创建一个隐藏列来维护每条数据的唯一性
整型大小比较比字符串快
插入自增主键效率更高，索引树调整小，如果非自增，索引树可能调整比较大
数据结构网站，可动态演示数据的插入查找过程：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html