mysql索引底层数据结构
一 什么是索引
索引是帮助mysql高效获取数据的排好序的数据结构，索引是储存在文件中的
1.1 图例
最简单的索引可以理解为目录（一行一行寻找），如下图所示
image.png
复杂一点的索引：树形结构索引
image.png
树形结构的索引效率要高于简单索引的效率
二 常见索引结构
- 二叉树（可能出现一边无线延长）、
如将col1作为索引字段，所有值插入二叉树中，右边一直增长
-
红黑树（可以自动平衡，避免单边增长，缺陷：每个节点只有2个子节点，第一层只能存1个元素（存一行记录的索引），第二层2个，第三层4个，只要表数据足够多，深度会无限的向下增长，这样如果数据如果在叶子节点，将会进行N次查询）
由上面可知：存储索引的树的高度越低，查找次数越少，查找速度越快。因此为了存储上千万行数据，并且还要让树的高度可控，只需要让一个节点横向存储更多的索引元素即B树
- hash（可以给索引进行hash操作，精确匹配一行记录只需要进行一次IO操作，缺陷：范围查找无法实现，适用于范围查找非常少的情况，同时mysql创建索引的时候，支持这种方式，但是很少使用，innoDB默认btree，修改hash保存会更改回来btree，只有memory引擎支持）
- B树
叶节点具有相同深度，叶节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列
把某列作为索引字段，将该字段的所有值存入B树
Mysql的索引结构，实际用的是B+ Tree，下图在col2上创建单列索引
这样就不是查询某个索引，而是将整个装有15,56,77索引元素的节点从磁盘加载到内存中，这样进行一次IO操作，就可以查询出很多索引。这样次数会少很多
- B+树
非叶子节点不存储数据data（索引所在行的磁盘文件地址），只存储索引，可以放更多的索引
叶子节点包含所有的索引字段以及索引所在行的磁盘文件地址
叶子节点用指针连接，提高区间访问的性能
非叶子节点会将叶子节点每个头元素，如15,20,49作为冗余的索引来构建B+树。实际的索引和data都在叶子节点层
每个包含很多索引的节点在mysql中叫做磁盘页，mysql给这个磁盘页分配的存储空间是16KB，可以使用下面的sql语句查询这个参数SHOW GLOBAL STATUS LIKE 'iNNODB_PAGE_SIZE'。即这个节点可以放16KB索引元素
假设要在B+树上查询30这个元素，首先在磁盘上定位根节点，将根节点整个load到内存，然后在内存中做比对，因为节点中的索引元素从左到右递增，因此可在内存中使用折半查找。发现在15到56之间，下图中的15和56之间的白色部分存储的是左分叉15,20,49的节点的磁盘文件地址，发现在做分叉，那就把15,20,49这个索引元素的节点继续加载到内存中去查找，然后去查找叶子节点，将叶子节点加载到内存，再折半，找到30
在内存中的比对操作相比于磁盘读取节点可以忽略不计
因为整张表的索引元素在叶子节点有一份完整的数据，假设B+树的高度是3，树被放满的情况下，求叶子节点可以放多少个索引元素？
每个节点可以放16KB的数据，如果存放主键索引，主键索引为bigint类型，而bigint一个占8个字节byte，而指向分叉的白色部分mysql分配占据了6个字节。而索引跟磁盘分叉地址白色部分是1:1的关系，当该节点占满后，可以放(16KB)/(8+6)byte=1170左右个索引元素。对于叶子节点来说，有点区别，因为叶子节点存放的data元素可能是索引所在行的磁盘文件地址，也可能是索引所在行的其他列，因此data可能有时候比较大，假设data是把一行的记录都放进来，单个索引+data最大按1KB算，那么叶子节点的一个节点可以放16个（索引+data）
那么H=3的高度的话，叶子节点能放1170x1170x16=21904200个索引元素
非叶子节点在mysql启动的时候，会一次性被load到内存中，那么比如查找30，上面的冗余节点不需要去从磁盘load，之前已经初始化在内存中了，最终只要在内存中定位到指定的磁盘地址指针，将叶子节点load一次到内存中查询即可
问：高度越低越好，那么直接将所有数据放在根节点处呢，直接一次load到内存？
不行，一个节点只能存16K数据，如果数据表真有千万行数据，也存不下，这个节点需要几M甚至几十M。况且每次查找都需要将这么多数据load到内存，或者load一次，如果有成百上千张表，放在内存也不现实，几千万的数据load到内存查找也不会很快
三 索引分类
- 普通索引
一个索引只包含单个列，一个表可以有多个单列索引 - 唯一索引
索引的值必须唯一，且不允许有空值 - 复合索引
一个索引包含多个列 - 聚簇索引（聚集索引）
不是单纯的索引类型，而是一种数据存储方式，索引和数据行放在一起存储 - 非聚簇索引
索引和数据行不放在一起存储
3.1 查看磁盘上innoDB引擎和myisam引擎的表实际存储形式
存储引擎是表级别的，意思是一个库中不同的表可以有不同的存储引擎，我们创建两张表用于测试，info表和info1表
info表采用innoDB引擎，info1表采用myisam引擎
innoDB引擎：
show global variables like "%datadir%"
磁盘上该表有两个文件
info.rrm 表的结构文件，任何一个存储引擎都有
info.ibd InnoDB独有的，（数据和索引）文件，即数据和索引在同一个位置
myisam引擎：
info1.frm
info1.MYD 以d结尾，代表data数据
info1.MYI 以i结尾，代表 index索引
3.2 myisam的非聚簇索引
如下图所示，col1第一列设置为主键，用B+树存储的时候，将所有的索引存储在叶子节点，索引15存储3个地方，做了冗余，叶子节点存储的是这一行数据库的文件指针（有了这个指针，再去文件中找一次即可）
先通过索引找到文件指针，再根据文件指针去MYD文件中定位那一行数据
col1创建的索引为主键索引，col2创建的索引为非主键索引，在myisam引擎中，存储的方式都是一样的
3.3 innoDB的聚簇索引
和myisam的非聚簇索引的差别主要在叶子节点，myisam在索引15的同一个节点中，存储的是行记录的文件指针，而innoDB在索引15的同一个节点中，存储的是索引所在行的其他列的数据，并且查到的索引15这一行数据才会加载到内存，没查询的还在磁盘上，因此不存在耗内存的问题
innoDB的主键索引存储形式不同于非主键索引，比如我们采用第三列学生的名字列作为普通索引，非主键索引叶子节点存储的data是索引所在行的主键
字符串的话，右边还是大于左边，采用ASCII码值的大小来比较左右
当进行匹配的时候，会把字符串转换成ascll码，如abc变成97 98 99，然后从左往右一个字符一个字符进行对比。所以在sql查询中使用like %a 时候索引会失效，因为%表示全匹配，如果已经全匹配就不需要索引，还不如直接全表扫描
（回表）innoDB有主键索引和非主键索引（辅助索引），先在辅助索引树上找到主键索引值，然后再用这个值去找主键索引树上对应的行记录
问题1：innoDB的非主键索引不存储整行数据，存储的是主键字段的主键索引的值，为什么要这么存储呢？
答：一致性和节省存储空间，主键索引已经要存储一次整行数据， 如果非主键索引也存储整行数据，那么意味着插数据要在主键索引和非主键索引都插入，插入两次，可能会有数据一致性的问题
问题2：innoDB表为什么必须要有主键，并推荐使用整型自增主键？
因为非主键索引存储的叶子节点会访问主键索引的地址，如果不使用整型，比如使用UUID的话，
（1）则浪费空间
（2）自增整型比较大小非常快，字符串作为索引，则比较采用ASCII码值逐位比较，速度极慢
（3）则每次新建节点申请一个页空间，即使如下图我只插入50，计算机也会申请一页的空间，而递增的主键id可以按照顺序进行插入，查询范围，比如大于50的数据，这一页会很快。而如果使用uuid的话，当前面满了他不会按照顺序在右面一直插入，而是会出现随机插入（比如插入在前面度满了的节点）这样导致这个节点会发生分裂，这是一个非常慢的过程，还可能该节点数据移动到其他节点上去，造成其他节点分裂
如果没有主键的话，innoDB默认会从你的记录中的能作为主键（数据不重复）的一列作为主键，如果一行的所有列都不能作为主键，那么innoDB会在后台默认生成整型主键
3.4 联合索引
不建议搞很多单值索引（浪费很多存储空间），优先联合索引
比如两个varchar字段key1，key2构成联合索引，存储索引的时候，是key1+key2字符串组合在一起进行比较大小的
三个字段，字符串类型名称，int类型年龄，字符串类型角色组成的联合索引
存储的时候，把这3个字段全部放到索引的这个里面，但是真正比较的时候是分开比较的，先去比较第一个字段，如果第一个字段相同就走到第走到第二行左边，判断第二个字段，如果还相同，就比较第三个字段
如果创建的是主键联合索引（联合主键），那么索引树的值中就存储行其他字段
如果创建的是非主键辅助联合索引，那么索引树的值中就存储主键字段
