Mysql索引底层数据结构与算法

索引

是帮助MySQL高效获取数据的排好序的数据结构。

B-Tree

•叶节点具有相同的深度，叶节点的指针为空
•所有索引元素不重复
•节点中的数据索引从左到右递增排列

B+Tree

•非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
•叶子节点包含所有索引字段
•叶子节点用指针连接，提高区间访问的性能

Hash

•对索引的key进行一次hash计算就可以定位出数据存储的位置
•很多时候Hash索引要比B+ 树索引更高效
•仅能满足 “=”，“IN”，不支持范围查询
•hash冲突问题
注：字符串要按照“ASCII”码排序，且占用空间比整型大。

聚集索引/非聚集索引

InnoDB索引实现(聚集)：叶子节点包含完整的数据记录(索引和数据一起存储)；
MyISAM索引实现(非聚集)：叶子节点包含内存地址(索引和数据分离)

二级索引

二级(Secondary Key)索引也是非聚集/稀疏索引，查数据的时候也是要做“回表”操作。

联合索引(最左前缀原则)

联合索引的底层存储结构长什么样？
1.先通过ascii码一个个比较字符串名字(name)中的字母排序
2.同名的再比较年龄(age)
3.最后同名同年龄的再比较字符串职位(position)
所以排序是根据创建索引时字段的前后顺序来定的
查询时也必须按照这个顺序来查，越往左的字段越必须，这就是索引最左前缀原理

select from user where name=’xxx’ and age=aaa;
select from user where age=aaa and position=yyy;
select from user where position=zz;
select from user where name=’xxx’ and position=zz;
只有第一个sql会走索引
第二个sql，因为年龄是乱序的，所以没有索引，只能全表扫描
第三个sql，因为position是乱序的，所以没有索引，只能全表扫描
第四个sql，只能走name索引

存储引擎的索引实现

MyISAM存储引擎

MyISAM索引文件和数据文件是分离的(非聚集)
非聚集索引(也叫非聚簇索引)，指的是在索引中最后一层的叶子节点记录的是地址，而不是实际的行数据，需要再通过地址去磁盘上找到数据


在磁盘中存储3个文件：
.frm:数据表结构相关的一些信息
.MYD:数据文件(MY表示MyISAM，D表示Data数据)
.MYI:索引文件(MY表示MyISAM，I表示Index索引)

InnoDB存储引擎

InnoDB索引实现(聚集)
聚集索引(也叫聚簇索引)，指的是在索引中最后一层的叶子节点记录的是数据，不需要再去磁盘中去找


在磁盘中存储2个文件：
.frm:数据表结构相关的一些信息
.ibd:索引+数据

重要：为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
因为MySQL的默认索引是B+Tree，有主键查询才快，如果没有指定主键，MySQL会默认自动生成一个 隐藏的 主键列，为了节省MySQL的消耗，因此建议自己建主键
整型：节约空间，好排序，好比较大小；若是UUID等乱序字符串，会很耗费空间；而且排序要把字母一个个转为ascii码再进行排序，且字符串本身也无法比较大小
自增：好排序，好比较大小，加上子节点双向指针更好的支持范围查找，而且在建索引树的时候直接往后开辟节点就行；如果非自增，如先插入8，再插入7，会导致索引树节点分裂，需要重新平衡，从而影响效率(性能)

注：
1.原本的B+Tree在叶子节点只有后继指针，MySQL在此基础上又做了优化，加上了前驱指针
2.对于MySQL自动生成的主键而言，主键是自增的，每次+1，数字是连续的，而对于索引而言，更看重的不是每次+1，它需要一种向上增长的趋势，数字不一定要连续

问题一：B-Tree和B+Tree区别？

B+Tree：非叶子节点不存储数据，只存索引；叶子节点包含所有索引字段和数据，并且双向指针连接，提高区间访问性能。
B-Tree：非叶子节点会存储数据和索引；叶子节点不存在指针连接；
叶子节点数据量越小，存放索引的数量就越多，树的高度就越小。

问题二：聚集和非聚集哪个快？

聚集，因为直接从叶子节点获取数据；而非聚集需要定位地址后，再次磁盘I/O从数据文件中读取数据

问题三：为什么非主键索引(辅助索引)的叶子节点存储的不是数据而是主键值(ID)？

保证了数据一致性和节省存储空间
如果一张表有2个分别独立的索引，每个索引最底层叶子节点都记录数据的话
1.会有多份同样的数据，只是不同索引最后数据的排序位置不一样而已(为了节省存储空间)
2.当更改数据时，要改2份数据(为了一致性)

问题四：Java 中的原子操作是什么？有什么好处

“原子操作(atomic operation)是不需要synchronized”，所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch；

使用原子操作的好处：
1. 性能角度：它执行多次的所消耗的时间远远小于由于线程所挂起到恢复所消耗的时间，因此无锁的CAS操作在性能上要比同步锁高很多；
2. 业务需求：业务本身的需求上，无锁机制本身就可以满足我们绝不多数的需求，并且在性能上也可以大大的进行提升。