引入索引
索引是帮助mysql高效获取数据的排好序的数据结构<br /> 由于一个表在磁盘中的存储位置并不一定是相邻的，因此当不使用索引查找一条数据时相当于全表扫描，直到匹配我们的条件。每次匹配都是一次I/O操作，效率不高，因此需要一种数据结构来帮助我们快速的定位减少I/O。这种数据结构每一个节点是一个键值对，key就是数据表这个字段的值，value则是该行记录在磁盘中的地址。<br /> 索引也存储在磁盘上，所以我们使用索引也是一次I/O
数据结构
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
二叉树排序树（二叉搜索树）
使用二叉排序树似乎可以提高效率，但是如果索引字段本身就是有序的，二叉树将会退化为链表，与不使用索引无异。
AVL树（平衡二叉排序树、平衡二叉搜索树）、红黑树
虽然二者能够让左右两边高度差最多为1，但是当数据量变多时树的高度将会越来越高，那么意味着需要的磁盘I/O也将变多
B树
特性：
1、所有叶子结点具有相同的深度，叶子结点的指针为空
2、叶子结点不重复
3、每个节点中的数据索引都是从左向右递增的
可以看出查找的次数与输的高度有很大关系，如果可以让节点存储更多数据，那么高度也随之下降了。而二叉树的节点也是存储在磁盘上的，要存储更多就把节点的空间喷配的大一点，每个节点的两个数据之间再向下分支，存储更多的数据
每个节点存放许多数据，每个数据仍然是键值对，15是表中的数据，data则是标一行记录的指针
度数为4表示一个节点存储多少数据要分裂，如下图如果再插入一个12，那么最右边的叶子结点将分裂
B+树
特性：
1、非叶子节点不存储data(磁盘指针)，只存储索引(冗余)，可以放更多的索引
2、叶子结点包含所有的索引字段
3、叶子节点用指针链接提高区间访问的性能
4、从左到右索引值也是递增的
B+树是B树的变种，B+树的非叶子节点不再存储磁盘的指针，而是存储“冗余索引”，如下图。B+树的叶子结点存储磁盘指针，下面的叶子结点叫做一个磁盘页，而上访的冗余索引则是每一页的第一个元素的key
mysql对B+树也做了优化，B+树正常是第二个图的样子，叶子节点是单箭头，而mysql中的是双箭头。相当于原本是单链表，mysql是双向循环链表（头尾也连在一起）
查找数据
例如查找col = 30，先从根节点开始查找，把根节点的数据加载到内存，由于是排好序的，那么在每一个节点上可以用二分查找。如下图，查找30，那么可以确定在根节点的15-56之间，15-56中间的白色代表的是大于等于15小于56的数据页的指针，继续向下找。最后找到30后把它对应的data拿到，根据这个磁盘指针取出磁盘对应地址的数据。 <br /><br /> 把每个节点I/O操作加载到内存与查找只在那个区间段亮着的时间后者远小于前者，可以忽略不计，也就是说通过索引查找绝大部分的时间消耗在把节点加载到内存。那么为了让加载的次数减少就需要让节点存储更多的数据。<br /> 那么既然查找的速度小于load的速度，那么为什么不把索引的所有数据放在一个节点上，这样只需加载一次？这肯定是不合适的，因为如果数据库的数据如果很多那么这个节点的大小肯定很大，要是有很多表都是这样的，把节点加载到内存会非常占用内存资源(把内存撑爆)。而且呢么多的数据即使二分查找很快查询的时间也不一定会快。而且数据如果很多几十兆几百兆大小一次磁盘I/O也加载不了那么多的数据
数据页
查看mysql数据页的默认大小
show glogal status like 'Innodb_page_size'
每一个节点在mysql中是一个数据页，一个数据也的大小是16384字节，也就是16k。假如索引字段的类型是bigint(8字节)，mysql底层为数据页指针(图中白色的部分)分配6字节，也就是说一个页可以存放16384/(8 + 6)个索引值和指针，大概1170个。<br /> 叶子结点有一个data，data可能是该索引值所在记录行在磁盘文件中的地址，也有可能是记录的所有其他列，这个data可能会比较大，与存储引擎有关。假设data是比较大的情况，放了一整行数据，大小为1kb(正常不会超过1kb，一个表也就最多几十个字段，除非存的数据比较大)，叶子结点这样一个数据页就可以存放16条数据。<br /> 也就是说一个3层的B+树根节点可以有1170个【索引 + 数据页指针对】，第二层就可以有1170 * 1170个【索引 + 数据页指针对】。第三层是叶子结点，每个【索引 + 数据页指针对】指向一个叶子结点，一个叶子结点可以存放16条数据，那么一颗3层的B+树全部放满可以放1170 * 1170 * 16 = 21902400条数据，而且实际上很大可能会比这多。<br /> 另外MySql会把根节点常驻内存中，高一点的版本会把所有非叶子节点全部放在内存中，因此仅需一次I/O操作，速度将会更快。<br /> 综上可以看出最终能存储多少数据取决于非叶子节点能存储多少索引元素
为什么不选择B树？
因为B树的非叶子节点也存储了数据(或者行记录的指针)，那么一个节点只能存放16条数据，如果也想像B树存放2000万数据那么就相当于 = 21902400肯定是大于3的(6.多)
超过2000完数据怎么办？
一般会分库分表，大不了再加一层，树的高度达到4将存储巨量的数据
存储引擎
数据库也可以设置存储引擎，但是具体表在使用存储引擎的时候使用的是表对引擎的选择而不是数据库上设置的引擎的类型，真正生效的肯定是数据库表的而不是数据库的。
数据文件
存储引擎就是数据在磁盘上的不同组织形式
MySQL的数据文件有xxx.frm xxx.ibd xxx.MYI xxx.MYD
.frm文件存储的是表的结构
.ibd存储的是数据，表示使用的是InnoDB存储引擎
.MYD存储的是数据，表示使用的是MyISAM存储引擎
.MYI存储的是索引信息，表示使用的是MyISAM存储引擎
因此可知对于不同的存储引擎可能有同样的数据结构，但是在磁盘上进行实际存储的时候表文件名称、格式都是不同的。例如：在InnoDB中索引与数据是存在一起的，在MyISAM中索引与问数据是分开存储的
MyISAM索引文件和数据文件是分离的(非聚集)
在Myisam中查找col = 30的记录，在MYI文件中维护了该表的索引结构，在找到叶子结点的data属性即索引所在行的磁盘文件地址，再根据地址去MYD文件找到对应的记录
Innodb的索引实现(聚集)
表数据文件(.ibd)本身就是按B+树组织的一个索引结构文件
innodb的数据和索引是放在一起的，放在.ibd文件中。使用innodb的表存储的回收就是B+树，叶子结点的data存放的是除索引外的该行的其他数据。
为什么推荐innodb的表要有主键而且是整形自增的主键？
为什么要有主键：
①因为inndb的数据文件必须要用B+树来组织的，如果表里面有主键那么就可以直接用主键来构建B+树
②如果没给innodb的表指定主键，也没有创建索引innodb会选择所有列中的一个值唯一的列（确切说会选择一个唯一非空的列作为主键）来构建B+树存储数据。如果没有值唯一的列mysql会创建一个隐藏的则6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。然后用rowid来构建B+树存储表中的数据，
综上一个表本来就应该有一个主键，这种事不应该来由mysql来做，我们选择一个列是很容易的
为什么整形？
在定位位置的过程中要在节点中比较大小，整形的数字比大小很快，而字符串要一位一位的按照AScII码来比较大小，速度不如数字
而且数字占的位置也比字符串要小，在生产环境中存储数据表文件的固态硬盘（SSD）资源有限，自然索引占位越小就能够节省空间
综上就是不使用字符串或者UUID的原因
为什么自增？
如果表使用自增主键
那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页
如果使用非自增主键（如果身份证号或学号等）
由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
聚集索引（聚簇索引）和非聚集索引（非聚簇索引）
聚集索引（聚簇索引）：叶子结点包含了完整的数据，一个表只有一个聚集索引。主键索引是聚集索引，但聚集索引不一定是主键索引
非聚集索引（非聚簇索引）：叶子节点是记录在磁盘的指针，不包含数据，稀疏索引也是一种非聚簇索引。非聚集索引需要回表操作，因为叶子节点没有保存全部的数据。
二者查找数据是那个更快一些？
聚集索引更快，因为查找B+树的时候找到叶子节点直接就能拿到数据，而非聚集索引还需要通过磁盘指针对应到相应的位置拿到数据
Hash结构索引
如果某一列使用hash结构的索引，会把这一列的每个值进行hash映射到一个hash表中。如果有hash冲突直接接在上一个数据后面。hash表中存储的值是一个键值对，key为索引列的值，value为这条索引所在行的磁盘文件的地址。<br /> 在查找name = 'Alice'时，先把Alice做hash，看映射到哪里，然后在遍历链表找到节点。拿出value值就可以拿到整条记录了<br /> 很多时候Hash索引要比B+树索引更高效，但是hash索引只能满足等值查询"="或者"in"，不能范围查询。另外还有hash冲突问题
B+树叶子结点的指针(范围查找)
查找clo > 20的所有记录，先从根节点开始定位到20在叶子结点的位置，由于B+树的节点中的值都是排好序的，并且叶子节点之间都有指针互相指向，所以找到20后只需要顺着指针找下去即可<br /><br /> 相较于B树，由于其叶子节点没有相连超过了数据页就需要从根节点从头查起，而且每个节点的数据页都存了数据，还需要记录每一次从根节点向下的路径。效率很慢
非主键索引(二级索引、辅助索引)
上面说的都是主键索引，二级索引如下图。依然是一个B+树结构，但是不同之处在于叶子节点存的不是该行的其他数据，而是该行的聚集索引的索引值。<br /> 这样做的目的是为了一致性和节约存储空间。一致性是因为如果二级索引仍然在叶子节点存储一行的值，那么如果表的值更改，这个表的所有索引都需要更改，存储聚集索引的索引值就不需要，只需要改聚集索引即可。节约存储空间是显而易见的。<br /><br />
联合索引(复合索引)
联合索引的结构
一个(“name”, “age”, “position”)的联合索引
最左前缀原理(最左列原理)
1、节点内数据的先后顺序
按照创建索引的字段的顺序来比较，也就是说先比较name，name相同再比较age，age相同再比较position。如果是聚集索引三个值不会都重复，叶子结点的data存储的是索引所在行的其他数据。如果是非聚集索引可能三个值有重复，但是叶子结点存储的聚集索引的列值不会重复
2、为什么最左前缀需要按顺序才能使用到索引？
因为节点内的值就是按照创建索引时的字段顺序排序的，跳过name去查age=30，并不是有序的不能正确的定位，只有在第一个字段是相等的情况下第二个字段age才是有序的，从整张表来看很可能不是排好序的。如果不按照顺序仍然使用联合索引，name查出来的结果可能不正确
问题
1、主键索引一定是聚集索引吗
2、如果表中没有主键，但是有一个值唯一且不为空的列，mysql会把它作为聚集索引。如果在后续的插入中该列出现了空值或者有重复值mysql会如何做？
3、刚创建表的时候没有数据也没有指定主键，mysql会创建聚集索引吗，如果创建是用rowid创建吗
4、刚开始没有指定主键，也没有唯一列，mysql是用rowid作为索引列。后面指定了主键mysql会改变聚集索引列吗
若有收获，就点个赞吧
0 人点赞
