索引

对于索引的理解

二叉树的索引结构：key存放索引字段， value放索引字段所在行的磁盘地址的文件指针

当执行sql语句时，会去找当前的字段是否建立了索引文件，如果拿取字段的值根据搜索方法（遍历）去索引结构找到对应的key，如果相等，则根据value磁盘地址的文件指针去找到对应的数据文件。而不需要进行全表扫描查询这样效率很低

使用二叉树（缺点：单边增长）

根据主键索引字段插入，使用二叉树会变成线性链表，跟表的轮询一样没区别，某些特定场景（单边增长，）效率太低

使用红黑树（数据多，元素在叶子节点查询次数多）

Jdk1.8对hahsmap的链表优化为红黑树（二叉平衡树），不会导致单边增长过分

索引底层使用B+树，当一百万表数据，红黑树的高度2的n次方 h=20可能

如果查找的元素在叶子节点 要查找次数久特别多，查个几十次

如何让使用查找次数到3-5，使高度为3-5？

使用B树（存储元素少）

一个节点存储更多的索引元素

使用B+树（存储元素多，且查询快）

mysql底层是B+树，对B树进行改造

B+树多了指针，非叶子节点只有索引元素，索引元素冗余

叶子节点存放所有的元素，上面一层存放中间叶子节点的元素（作为冗余）

如果B+树一次性放全部节点在一行，如果数据扫一次性得加载很多的内存，时间，浪费内存

为什么要冗余？同等大小只存储索引的话，可以存储更多的索引，因为不存储数据，这样磁盘加载的次数就少了很多

• B+树（多叉平衡树）索引元素占用bigint，8bit

• 空白地方指向下一个大节点的磁盘文件的地址指针，占6bit

• 存储一个索引需要14bit 8+6，默认给了16k，16kb/14b=1142

• 叶子节点没有空白节点，data设置为1kb ，16/1=16 这棵树可以存储16个索引元素

1170117016=2100w差不多

一般树的第一行node根节点放放在内存，其他放在磁盘

树的高度3，就可以存储几千万行的索引元素

磁盘是做io，如果io多的话，性能很低

建索引千万级别的表，几百毫秒，不建索引要几十秒

使用B+树和B树的区别

• 因为数据库的一个节点大小为固定16k，B树需要存储数据，所以它的树高，
• B+树的非根节点只存储索引，所以树矮，

根节点是存在内存当中的，其他非叶子节点存在磁盘，遍历的时候需要进行磁盘加载

因为B+树矮，所以进行磁盘加载的次数就少了

数据库文件的存放（表结构，数据文件，索引文件）

存放在数据库文件夹的data目录下的数据库目录

存储引擎为MyISAM，frm为表结构，MYD数据文件，MYI索引文件

存储引擎为innodb，frm表结构，ibd数据文件和索引文件

关于存储引擎myi的原理

myi是存储索引元素，而索引元素由B+树进行实现的

当我们发起一条select *from t where col1 = 49

1.先根据字段col1判断是否是索引元素（也就是是否建立了索引）

2.建立了索引则根据值49去根节点去查找，根节点是常驻内存的，一直往下找

3.进行比对，找到key=49索引元素，对应的data存放的是索引所在的那一行的磁盘文件地址的指针

4.拿到指针后，去到myd文件，快速定位到这一行

关于存储引innodb存储原理

当我们发起一条select *from t where col1 = 49

1.先根据字段col1判断是否是索引元素（也就是是否建立了索引）

2.建立了索引则根据值49去根节点去查找，根节点是常驻内存的，一直往下找

3.进行比对，找到key=49索引元素，对应的data存放的是索引所在的那一行的数据文件

为什么innodb的表必须有主键，并且推荐使用整形的自增主键？

• 没有建立主键， innode会在表里找一列可以唯一索引帮你建立主键，
• 如果找不到，默认加一列数据，建立一个主键，能够标识唯一数据，后台帮你组织维护

不用整形主键，使用uuid（随机流水号）,

• B+树进行比较，整形比较大小更快更高
• uuid，字符串比大小，还要转成asii码，进行比较
• uuid的占用空间大，磁盘空间使用更大，整形小，

为什么使用自增？

• 用uuid来维护索引，如果算出来的值是比较小往中间插入的且在一个满了16kb
• 这样就需要进行分裂，平衡，向上合并，导致高度变高

< >= 从左到右递增

递增，指针方便快速找到下一个节点

聚集索引和非聚集索引

聚集索引：叶子节点包含了完整的数据记录 ----查找一次 ，ibd ，效率更高

非聚集：myisam索引文件和数据文件分开存储-----------查找两次 ，myi -> myd

哈希索引

底层使用哈希表，散列 hash（值）=散列值

去哈希表定位/映射到索引所在的那行的磁盘文件地址的指针

经过一次哈希运算知道索引所在的那行的磁盘文件地址的指针

Md5底层就是哈希算法

Select * from t where vol1 = 6 比B树快

缺点：

但是Select * from t where vol1 > 6 ，只能定位到6，大于6的数据无法定位

范围查询就gg，缺点对范围查找不行

如果是B+树的话，根据20找到对应的，根据大于或者小于直接指针顺腾摸瓜

B树很麻烦，需要查询很多次，磁盘加载次数就多