一、索引数据结构

mysql数据存储在磁盘，每次遍历一个节点，相当于与磁盘进行一次IO，加载到内存。

二叉树：当存储递增类的索引，退化成链表

红黑树（hashmap底层）：自我平衡旋转，实际情况可能放几百万记录，如果查叶子节点，树的高度太高，仍然进行IO很多，效率低

B树：每个节点初始化分配大一些，可以存储多个索引，而且每个节点支持分叉

B＋树：索引元素data（索引所在行的磁盘文件地址\磁盘列数据）都放在叶子节点，

每个16KB的页节点第一个索引元素作为冗余索引

白色区域是索引所在磁盘文件地址，说白了就是指针

如果索引类型bigint:8B,16KB/(8+6)B=1170  

date+索引元素大概占1KB，16KB/1KB=16

能放索引个数：1170*1170*16

非叶子节占得存储空间不大，mysql在启动的时候可以加载到内存，所以关键就叶子节点做一次磁盘IO就搞定了。叶子节点双向链表，节点之间通过指针域存放的地址顺序连接。

存储引擎，作用于数据库表的。

我们的数据库表都以多个文件存储在磁盘中（mysql文件夹的data文件里）

MyISAM

frm：存储表结构  MYD：存储表数据   MYI：存储索引

查找数据：先查MYI文件，再根据查到的地址，去MYD文件查询（回表操作）

InnoDB  frm和ibd（数据和索引）  查数据遍历一个文件

面试题：

1聚集索引和非聚集索引的区别

2主键索引和二级索引的区别

3为什么建议InnoDB表必须建主键，推荐使用整型的自增主键

4为什么非主键索引结构叶子节点存储的是主键值

3--答案：

Mysql设计开发的时候就设置了需要索引，去组织数据。当未手动设置主键索引时，InnoDB会从第一列开始遍历，找一列数据（如果可以做唯一索引），用这列数据维护B+树。

如果没有找到，Mysql会用它自己的隐藏行（rowid）为每行数据建索引，但这个消耗mysql的性能（宝贵资源），推荐手动建，查起来方便。

遍历节点会涉及到比较，整型与整型值查找性能高。如果是UUID，则先需转ASCII码，再逐位比较，前面位相同情况下，可能会比很长的位。

性能要求比较高的公司，数据库存储在SSD（昂贵的固态硬盘，存储空间宝贵），整型占空间小。

为什么主键要自增？如果随意次序的主键值插入，会导致节点分裂（元素挪动）费时间。

hash

索引的key进行hash运算，模长度得到节点位置，如果是空，则将索引值和索引所在行的磁盘文件地址往进来，如果很多元素，往后加就行。

hash运算公式相对于磁盘IO是相当快的，O(1)的级别，直接定位节点。但是不支持范围查询，会全表扫描。InnoDB叶子节点存储相邻行元素磁盘文件地址，顺藤摸瓜查到目标。

工作中，常用的是联合索引（一张表，2个左右联合，一个单只有时候不一定建）

联合索引，按顺序，先按name排、再按age、position。联合索引生效的前提，前提查询从索引的最左前列开始且不跳过索引中的列。这样的是索引是排的有序的。

只有1走索引。

单纯扫age=30,从左到右扫叶子节点，扫到第一个，还需继续往后扫，扫完全部，因为不是按age有序排的。

语句：select * from employee where name = 'Bill' order by position; //触发filesort。因为只name查到的数据，得到的并不是排好序的。

select * from employee where name = 'Bill' and age = 30 order by position; //name和age走索引。position并没有用文件排序，其实用的就是索引排序。前两个已限定情况下，查到的position就是有序的，不需要在文件中再排序。

工作中，95%以上的都是单表查询（单表走索引效率高），多表关联底层复杂，大量过滤，计算，算法可能导致mysql查询慢，走索引走的不好。

索引规约：超过3个表禁用join。需要join的字段，数据类型保持绝对一致，多表关联查询时，保证被关联的字段有索引。即使双表查询也要注意索引，SQL性能。

二、事务

undo log日志：当插入一条记录时，隐形的一个字段存放着指向undolog的指针，指向delete语句。

MySQL默认：RR   Oracle默认：RC

读已提交问题场景：一个事务更改了字段，事务2查询得到值，此时当其他事务更改此字段，事务2 再查出来的值是不同的。相当于一方法里，读了多值，以哪个数据为准。

可重复读：在当前事务里读，以第一次读的表（最初的快照，包括每个行记录）为准，后续此事务中，查询结果为第一次的表的值。

串行：别的事务在做更新操作，另一个读事务就得阻塞等待其提交后，才能查。读写串行执行。底层实现原理：mysql在后台给select语句加了读锁，读写锁互斥，实现串行。

Copy on write 读写分离

如果读写同一份，可能存在读到修改部分数据的脏数据，如果加锁实现读写串行化，性能会低。

问题：读旧数据问题（RR）。在微服务架构中，是能容忍的，例如如果读到地址不存在，失败了重试，高并发的妥协一下下。

每条记录有两个隐藏字段，一个是事务id，一个是回滚指针，指向undo日志语句。

多版本并发机制：读写分离的Copy on write。读，读的是历史的快照数据，写，写的是副本数据，读写分离进行。性能提升。

每行记录的更改都有版本链

开启事务更新balance字段500---》800----》1000 形成一个版本链。

读已提交，读的是最新的，也就是最后的数据状态。

可重复读，是当前事务和已提交的第一次更新的值有一个绑定关系（可见性算法），后续从版本链中都是找我们第一次查询的绑定的那个数据。

如何避免读旧数据：

1乐观锁：设置版本号。更新字段时，是以Copy On Write机制作用于副本数据上去update，带上一个version条件，如果和select查（可重复读会使事务查到的都是第一次快照数据）到的version一致，则更新，否则更新失败，重新查，获取新的版本数据进行更新。

第一次查询select * from account where id = 1;//500,version = 1

代码逻辑：500-300=200；但其他事务已修改balance为1000；

update account set balance = 200 where id = 1 and version = 1;//update语句查询版本号为4不等，重新查。

2悲观锁：update会加锁，实现串行化拿资源。说白了就是每次都是拿到最新的数据。作用于最新数据记录。

update account set balance = balance - 200 where id = 1;

查询操作需要使用事务吗：

如果隔离级别是可重复读，多条查询语句，那么需要开启事务的。

例如，我第一次查李磊账户1000，此时有人修改了韩梅梅的账户1000-》8000，如果没有设事务，我这次查韩梅梅的就是8000，我要基于李磊和韩梅梅的生成数据报表，但此时两人数据不是同一时刻的。所以要开启事务，保证查，查的都是同一个快照数据，数据一致性。

阿里内部大多用RC，传统软件公司更多用RR。大多数电商网站对性能要求较高，传统公司类似做ERP里面很多报表，基于时间点的的结果，数据一致性高。 

三、redo日志实现持久性

更新数据，先查询缓存池是否有这个数据，如果没有，查询加载磁盘文件到缓存池，进行更新的同时写入undo日志，更新内存，写入redo日志（记录哪个页哪个记录被修改了什么，物理修改），当Mysql宕机了，重启后进行读redo log将数据重新加载到内存。事务提交成功，redo日志就会写成功，idb文件数据库底层有异步的IO线程在后台进行随机写。

为什么这样设计这个机制：

像kafka，单机10+，性能高，底层是磁盘顺序写

磁盘顺序写，跟内存随机读性能接近，比磁盘随机IO,随机读，高很多倍。其实就按物理磁盘的位置写入相应的位置。

但是ibd文件不能顺序写，数据库表是不同的ibd文件。并且数据库表涉及到删数据，空白内存需要后续的数据放入，不能实现顺序写。redo日志是一个文件可以实现顺序写，并且它都是在文件后面追加，即使删也删最前面的。