MySQL数据结构
二叉树
将新增数据插入左右两边，如果比节点数据要小，则放到左边，比之大放到右边。
但如果列数据一直递增，那它就变成了一个链表结构。当要查询某一数据时，需要一直遍历该链表进行查找，效率极低。
红黑树(二叉平衡树)
红黑树又名平衡二叉树，其本质还是二叉树，但其内部会进行平衡左右两边的数据，解决了普通二叉树数据一直递增最后成了链表的问题。
但如果数据量较大时，那它树的高度会相当高，查找次数即同样相当多，效率也很低。
B树
叶节点具有相同的深度，叶节点的指针为空，所有索引元素不重复，节点中的数据索引从左到右递增排列。
B+树
B树的优化版，非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引，叶子节点包含所有索引字段，叶子节点用指针连接，提高区间访问的性能。
mysql一个叶节点存储空间大小为16kb，最顶部叶子节点存储的data，可能是真实的行数据，也可能是行数据所在的磁盘地址。
什么是索引
在关系型数据库中，索引是一种排好序的数据结构。它将数据提前按照一定的规则进行排序或组织。能够帮助快速定位到具体数据，加快数据表中数据的查找和检索。
比方说：书本的目录，文件夹、标签、房号等。都属于是索引，都可以帮助我们快速进行目标数据的定位。
其本质是帮助MySQL高效获取数据的排好序的数据结构，设计思想是以空间换时间。
索引的总类
MySQL中的索引是在存储引擎层实现的，而不是服务器层。所以不同的存储引擎具有不同的索引类型和实现，常见的索引分类如下
按照数据结构分类：B+树索引(所有引擎都支持，最常用)、Hash索引(仅Memory引擎)、Full-text索引(InnoDB、MyISAM)
按照物理存储分类：聚集索引(InnoDB主键索引)、非聚集索引(MyISAM、InnoDB非主键索引)
按照字段特性分类：主键索引(primary key)、唯一索引(unique)、普通索引(index)、全文索引(fulltext)
按照字段个数分类：单列索引、联合索引
B+树索引
当一个表没有设置主键索引的时候，还会生成B+树吗？
答案是会的，在InnoDB引擎中，它会给每个表创建主键索引。如果没有明确的主键索引，InnoDB会使用一个自动生成的、隐藏的主键来创建索引（row_id）。
这个隐藏的主键索引使用的就是B+树结构，所以，InnoDB中，即使没有明确的主键索引，也会创建一个B+树索引。
Hash索引
【注】Hash索引在InnoDB中，不支持显式的创建。虽然可以使用sql语句声明Hash索引，但其实是不生效的，在底层仍然使用的是B+树索引，Hash索引仅限于Memory引擎中。
比方说现在把表字段name声明为Hash索引，假设此时有三条数据，分别是：张三、李四、李四。
Hash索引会将它们的名字通过Hash算法计算出一个Hash值，存放到一个槽里，然后对应其数据。但此时的Hash值有可能冲突，比方说上面假设的同名“李四”。
此时会将数据存成一个链表，当要查找name为“李四”时，首先找到对应 Hash的数据（链表），然后遍历其链表，找到要找的值。
Hash索引
优点：只能用于等值比较，效率非常的高
缺点：不支持范围查询，不支持排序，因为索引列的分布是无序的
聚集索引 和 非聚集索引
按照物理存储分类：聚集索引(InnoDB)、非聚集索引(MyISAM)
test_innodb.frm => Frame表结构
test_innodb.ibd => Innodb data表索引+数据
test_myisam => Frame表结构
test_myisam.MYD => MyISAM data表数据
test_myisam.MYI => MyISAM Index表索引
当通过id查询时，聚集索引比非聚集索引更快。非聚集索引的叶子节点只保存了数据个地址，当查询寻址找到对应的目标时，还需要通过该地址去找到对应真正的数据
二级索引：InnoDB里面，非主键索引都是二级索引。例如，在user表，给age加了一个索引。此时这个即是二级索引，二级索引是非聚集索引，其他数据不存放在叶子节点上，叶子节点存放的是主键的id。当通过二级索引查询到指定数据时，会得到对应主键的id，通过【回表】操作，重新找到该id的主键记录，得到其数据，当然了，如果只查询id 比如：select id from user where age = 25，此时则不需要进行回表了，因为叶子节点存储的已经是对应的id了，这个过程称之为【索引覆盖】，所以，在实际开发的过程中，应尽量少使用select * 进行查询，通过【索引覆盖】可以部分加快查询。
单列索引 和 联合索引
单列索引
假设现在有user表，字段有：id，name，age，sex。
此时给name字段设置了一个普通非唯一索引：alter table `test`.`user` add index (`name`)，那么name就是索引列，同时也是单列索引
联合索引
区别于联合索引，假设上面的例子中，给name和age建立一个联合索引:alter table `test`.`user` add index (`name`,`age`,`sex`)。
当排序时，是先给name进行排序，name相同时接着给age排序，如果还有其他的列时，以此类推，最后再以id来排
最左前缀原则：当创建了联合索引的时候，想要索引生效的话，必须要带上最左的字段，例如例子中的name，只能使用：name/age、name/age/sex、name/sex 三种组合。例如：select name,age,sex from user where name = '张三' and age = 12
联合索引的优势
减少开销：建立一个(a,b,c)，实际相当于建立了(a),(a,b),(a,b,c)三个索引，每多一个索引，都会增加写操作的开销和磁盘空间的开销，当在大数据量的表，使用联合索引会大大减少开销。
覆盖索引：select 不使用*，而是直接指定联合索引的字段，此时查询出结果后，不需要进行回表而能直接得到数据，在实际的应用中，覆盖索引是主要提升性能的优化手段之一。
效率更高：相对于单列索引，当假设要查询name、age、sex字段时，假设设置了3个单列索引，在找到数据时，因为其并非主键索引，叶子节点存放的只是主键id，因此还需要多次通过该索引得到的id回表得到整条数据的内容，而联合索引只需要回表一次即可得到整条的数据内容
索引的优缺点
优点
1.提交检索效率，更快的查询出结果
2.降低排序的成本，索引对应的字段都有一个自动排序功能，默认升序asc
缺点
1.创建和维护索引需要耗费时间，这种时间随着数据量的增加而增加
2.索引需要物理存储空间，数据量越大，所需的空间越大
3.降低数据表增删改的效率，因为每次增删改，索引都要进行动态维护其树结构
为什么建议InnoDB表必须建主键，并且推荐使用整形的自增主键？
建主键
如果不建主键，则mysql内部会根据列数据去构成一个B+树索引。
如果所有列都不满足，则自动生成一个隐藏列来构建，不但空耗空间，还因为是隐藏列外部无法使用，故而自己使用主键为更优解
整形
效率更高(直接比较整形比ASCII码后比较更快)且更节省空间
自增
因为b+树索引为排序后的，如果不是自增，则可能需要在某两个数据间插入一条新数据，可能导致节点分裂。
而自增则在最后面累加即可，前者效率会更高，而使用uuid的话，可能会高频出现从中间插入数据，非常影响性能。
但如果是偶尔从中插入，这种情况是可以的，比方说分库分表中用到的【雪花算法生成id】，它是趋势递增的，偶尔会从中间插入
