[toc]

选择数据类型的原则：#

• 越小越好。 如果后续因为业务需求要alter增大范围， 会很耗时。
• 简单数据类型， 比如用整数而不是字符串去存ip。
• 尽量NOT NULL。原因:索引列如果存在null， 会需要一个额外的字节，? ?索引统计也变复杂了。

整数类型：#

• mediumint是24位的， 其他分别是8、16、32、64对应tiny、small、int、big
• 支持unsigned属性
• int(11)不代表用11位存储， 限定只是在客户端工具中只显示11位字符。

实数类型（带小数点的类型）#

• 有时候不一定是为了小数才选实数。 比如选decima而不是bigint是因为decimal可以存储比bigint还要大的数字
• float和double就是标准的16、32浮点运算
• decimal存储精确的小数和精确计算（精确计算只在mysql5.0之后）
• 浮点比decimal要的存储空间更小， decimal(18.9）会用掉9个字节（4小数点前+4小数点后+1小数点本身）
• 只有精确计算才用到decimal， 如果数据太多，为了节省空间， 可以改成用bigint（只要把小数点部分乘10的倍数，去掉小数点即可），毕竟decimal比较耗空间。

字符串类型#

varchar#

• 存储可变长字符串。（例外： 用ROW_FORMAT=FIXED创建的话，varchar的空间会固定）
• 可变长的概念：
  char是固定长度的，例如你定义了12，插入了"aa"，后面它会给你补10个空。如果是varchar，那么"aa"就是"aa"不会给你补
• varchar(N)代表的N是最大长度
• 需要1-2个额外字节， 来保存字符串长度
  varchar(n）需要的最大存储空间长度= n + (n<=255?1:2)
• 2种情况不适合用varchar

1. 最大长度比平均长度要大
2. 列的更新很少

• varchar(5)相比于varchar(200)的优势： mysql会分配固定大小的内存块来保存内部值。尤其是使用内存临时表进行排序或者操作时会特别糟糕？？ 不懂

char#

• char是定长的，因此总是会预留足够的空间
• char存储时，会删除字符串末尾的空格。 即’ abc ‘存入后，会变成’ abc’
• char相比varchar的优势： 字符串很短时， 需要的空间比varchar少(varchar需要额外空间存储长度)

binary 和varbinary#

• 存储的是二进制字符串（字节码，0x77那种）
• binary 采用\0而不是空格来填充
• 二进制字节码比较的速度比字符快

BLOB和TEXT#

• 为了存储超大的数据而设计的字符串类型
• mysql把他们当作独立的对象处理，专门使用外部的存储区域来存储， 内部存储指针。
• BLOB和TEXT的区别： 一个是二进制，一个带有字符集规则
• mysql对这2个类型做排序时， 只对前max_sort_length字节做排序
• 因此不能将这2个类型的字段做索引

枚举enum#

create table enum_test(e ENUM(‘a’,‘b’,‘c’) NOT NULL)

• 实际上存储的不是’a’这个字符串，而是1\2\3 这类数字
• 按照定义顺序分配数字
• 排序时也按照实际数字排序，而不是枚举的字典序
• 枚举作为主键也优于字符串， 毕竟她本质是数字。但是比数字会差一点。

日期和时间类型#

DATETIME#

• 从1001到9999年， 精度为秒
• 与时区无关
• 使用8个字节存储

TIMESTAMP#

• 从1970.1.1至今的秒数
• 只使用4个字节
• 显示依赖时区，服务端、客户端都需要配置时区，然后timeStamp的展示就会不同。
• TIMESTAMP默认为NOT NULL
• 插入时会自动设置这个列的值为“当前时间”

如果想存毫秒怎么办？ 可以使用bigint来存储毫秒级时间戳。

位类型#

通常用于存储acl权限

bit（n)#

• mysql把bit当作字符串而不是数字类型
• 存储00111001并且检索时， 得到的ASCII为57的字符串（即’9’)。 在数字上下文场景却是数字57
• 因为这个特性，慎用bit

set#

• 如果字段内容就是一堆true或者false的位，可以放到set类型种
• 替代方式： 用tinyint类型来替代， 就是比太好理解。

主键的选择#

• 整数是坠好的
• enum和set是糟糕的选择。
• 字符串类型也尽量避免。空间大，检索慢
• 避免随机生成的主键字符串，原因:

1. 插入值会随机写到索引的不同位置
2. select语句会变慢
3. 随机值导致缓存失效( 局部性原理gg）
   因此最好不要用string类型的UUID， 而是转为数字。

schema设计时的陷阱#

• 太长的列且列中有变长的字段， 可能会导致转换成行数据结构时要消耗很大的CPU。（从行缓冲种将编码过的列转成行数据的缘故）
• 表的关联表太多会有问题。 建议查询最好在12个表内做关联。
• 防止过度使用枚举。 枚举的缺点:
  ① 可能会有人搞一个enum(‘-1’,‘0’,‘1’,‘2’)这种误导人的枚举
  ② 每次要新增枚举必须alter table，会阻塞表
• set中的元素如果每次只能出现一个， 应该改成枚举。
• mysql会在索引中存储null，但是oracle不会。
• 尽量不要用null，而是用空字符串、默认值替代，除非没有可以用的默认值，宁愿用null去引起调用方注意

范式的考量#

范式设计： 每个数据一般只会出现一次，没有冗余或者重复数据
反范式： 与范式相反。

范式的优点：

• 更新操作快，因为重复的记录少
• 表更小，可以更好地放到内存里
• 很少需要做distinct、groupby， 因此一般都是1对1的关系

缺点：
查询时经常需要关联，当关联后的另外一个表需要做条件判断，可能会消耗一定性能

反范式的优缺点和范式正好相反。

查询的缓存#

• 有时候会弄一个叫缓存表或者汇总表的东西， 避免每次查询所有记录来得到一个区间的结果
• 计数器表，如果表里只有1行，可能导致并发效率低。 可以弄100行，然后大家更新时随机更新。 统计结果时直接sum即可

alter table性能问题#

• mysql中， alter table的原理一般是 用新的结构创建一个新表，然后把数据导入到新表中。
• 有一些操作可以只修改表的.frm文件来达到修改结构的作用。
  比如 alter column修改默认值， 移除列的auto_increment属性， 或者修改enum、set的常量 （可以通过弄一个新表，然后只修改新表的属性，接着进入数据库后端直接替换tablename.frm文件

分区的限制#

MySQL分区的限制

• 一个表最多只能有1024个分区。

• MySQL5.1中，分区表达式必须是整数，或者返回整数的表达式。在MySQL5.5中提供了非整数表达式分区的支持。

• 如果分区字段中有主键或者唯一索引的列，那么多有主键列和唯一索引列都必须包含进来。即：分区字段要么不包含主键或者索引列，要么包含全部主键和索引列。

• 分区表中无法使用外键约束。

• MySQL的分区适用于一个表的所有数据和索引，不能只对表数据分区而不对索引分区，也不能只对索引分区而不对表分区，也不能只对表的一部分数据分区。

分区详细用法

[toc]

查询为什么会慢？#

• 查询的生命周期
  客户端发送->服务器接收->服务器解析sql->生成执行计划->执行->返回结果
  其中最耗时的就是执行了。
• 查询执行时耗费的时间：

1. 网络
2. CPU计算
3. 生成统计信息
4. 锁等待
5. IO操作

应用逻辑上处理低效查询#

应用层逻辑上，是不是返回了太多会被自己抛弃的数据#

这个主要和 返回的数据有关

• sql里写的是返回所有行， 却在代码里只取resultSet的前10行。
• sql里写的是返回select *， 代码里却只需要特定几列。
• 每次查询肯定是相同的结果，却没有做缓存。

mysql中，是否在扫描额外的记录#

这个主要和查询的过程有关（返回的数据已经优化到最优了)

• 扫描的行数/返回的行数的比值越小越好
• EXPLAIN分析中有几个type，从坏到好分别是

1. 全表扫描All
2. 索引扫描ref
3. 范围扫描
4. 唯一索引查询
5. 常数引用
   EXPLANIN里会显示扫描的行数row， 你可以和返回的行数做对比

• mysql中有3种方式来使用where条件，从好到坏分别是

1. 在索引中直接做where判断来过滤，然后返回底层数据，这个需要在存储引擎层完成
2. 索引覆盖扫描，直接在索引中返回数据，没有走到底层的数据处，这个在服务器层完成即可，不用走到底层存储引擎
3. 先从存储引擎返回数据， 然后再在服务器层做where判断来过滤

• 为了减少扫描的行数，常见优化方式：

1. 使用索引覆盖扫描
2. 使用汇总表（就是每次做一些操作就会触发更新，不要再去重复查询了）
3. 重写复杂查询(联结等）

重构查询语句#

limit切分查询#

• 指的是用limit等分页手段来切分，分多次执行
• 适用于一些可能会锁表的大批量操作。
• 比如删除某10w条数据， 最好先查询+limit 1w，分10次执行，中间间隔一些时间， 避免长时间的锁表。

关联查询（join）分解#

• 如果一个语句中join多次， 看下能不能在应用层分3个select依次执行，每次取前一次select的结果加入自己的条件中
• 好处：

1. 分解后条件变简单了，就有可能利用mysql的缓存。
2. 也因为条件变简单且是单表，可能会利用上索引
3. 减少锁的竞争
4. 每个表相当于只查询了一次， 减少了重复访问。

优化In查询#

1

select * from a where id in (select id from b where b.xx<y)

注意上面并不是先计算in子表返回的内容，然后作为条件去做检查
而是变成一个关联查询

select * from a where exist(select * from b where b.xx<y and a.id=b.id))

会先对file表做全表扫描，然后再进行条件查询。这这会很慢

• 改进：

1. 用inner join改写成内联
2. 用GROUP_CONCAT生成一个列表，再提供给IN去使用。
   P 224-225

优化UNION加limit#

（select …） UNION ALL (select …) limit 20
这句话本质上会把需要联合的表全部取出，做合并之后，再limit，如果表很大，limit相当于没有他本该的作用。
可以改成 在内部都加上一个limit来减少union时的量

索引合并优化#

等值传递#

IN（）列表可能会被复制到关联的各个表中， 列表很大就会导致执行变慢

并行执行？#

mysql都是单线程进行查询

哈希关联#

• mysql不支持哈希关联， 关联都是通过 嵌套循环关联的。
• 除非用之前提过的自定义哈希索引部分（弄一个触发器来生成哈希索引）

松散索引扫描#

指没有用到第一列索引，却需要用第二列索引时，按照下面的方式去查：

select * from xxx where B = xxx group by A;
添加 group by 字段后，会先根据 A 索引分组后，会在每个 A 的范围内使用索引进行快速查询定位所需要的 B 列，这就叫做松散索引扫描，比新建一个索引的效率会慢 A 的 distinct 倍，但省去了新索引的消耗

最大和最小值优化#

如果你MIN（）的是主键，且where中没有用到索引， 那么MYQL就进行全表顺序扫描。
扫描时按理应当满足第一个可行的值时，就是最小值（主键按顺序排列）
但是mysql不支持。
可以用limit 1来优化，不要用MIN或者MAX， 如果你要统计的是主键的值的话。

同表查询和更新#

mysql不允许 在同一张表进行查询和更新

优化Count()#

• count(列或列的表达式) 会过滤掉无值或者null的情况。 而count(*)直接统计所有行数
• count(*)的性能好一点， 因为他不用过滤和比较是否为空，可以直接用存储引擎记录的一些信息直接得到。
• count(*) 不带where非常快， 如果带了where，就要遍历。
• 一种优化： 如果统计where id>5， 而id>5很多，<5却很少，可以反向求接，改成
  select (select count() from city) - count() from t where id < 5。
  毕竟不带where的是很快的。
• 如果对计数要求不是那么精确， 可以用汇总表去处理总和的问题，每隔一段时间更新一次。
• 注意这种用法
  select count(color=‘blue’ OR NULL) AS bule, count(color=‘red’ OR NULL) as red from items;
  可以求红色和蓝色的个数并展示在同一行中，无需分组。

关联查询优化#

• 确保ON或者USING的列上有索引
• 如果B join A， 那么A上有索引足够了。因为联结是是遍历B的每一行，拿B的joinKey 去A里面搜索，所以真正用到的是A的索引（除非执行计划做了优化）
• 优化GROUP BY 或者DISTINCT

Group by优化#

• 分组时，要么利用文件要么利用内存做临时表，你可以用优化器的提示去控制用内存还是文件
• join后再分组， 分组里的列尽量用join的key， 比如你虽然是要按名字分组并栈式的，但名字和id是一一对应的，所以按id分组并展示名字是ok的
• 不要用分组去展示非分组列（即不是聚合结果也不是分组列）
• 分组时，会自动对分组后的结果按分组列排序，消耗一定时间。 如果不希望排序，可以加一个ORDER BY NULL

优化LIMIT分页#

• 对于“LIMIT 100000,10” 里面存在100000的偏移，而偏移本质上得扫描掉前面的100020条记录。
• 有3种优化方式：

1. 构造一个联结临时表，临时表里做索引覆盖查询+limit（即select的只有limit列），然后再拿得到的id做联结，获取你需要的列。
2. 如果确定是某个limit的范围，且为索引，则用where 索引范围来代替
3. 或者where xx<100020 ORDER BY XX DESC LIMIT 20来反向求。

如何知道是否有下一页?分多少页？#

1. LIMIT的时候加上SQL_CALC_FOUND_ROWS。这样会返回除去LIMIT之外的其他行数，相当于剩下还需要的行数。
2. 每次LIMIT X+1， 应用层只拿X行， 如果有多一行，说明还有下一页
3. 每次LIMIT 10X， 然后10X作为缓存，应用层每次取X作为一页展示。

优化UNION#

• UNION的本质是创建并填充临时表
• 用UNION ALL， 否则会默认加上DISTINCT关键字进行唯一性检查，消耗性能

使用自定义变量优化#

见6.4自定义变量

用特殊关键字控制执行计划#

• High_Priority/low_priority
  多个语句同时操作一个表时， 可以用这个来控制语句的优先级。
• Delayed
  对插入和更新操作而言， 他会直接返回响应给客户端，然后把数据缓存下来，等服务器空闲了再去插
• Straight_join
  可以用这个关键字控制 join顺序，而不是用优化器的join顺序
• SQL_small_result
  告诉优化器 结果集很小，你可以搞个内存临时表做排序
• SQL_big_result
  告诉优化器 结果集很大， 可以提早准备磁盘排序而不是等发现不够了采用磁盘。
• SQL_CACHE
  结果集是否应该缓存。
• SQL_CALC_FOUND_ROWS
  让返回的结果集包含更多信息（例如limit 10,结果集里却有个总数信息）
• For update / Lock in share ode
  提示优化器加行锁
• Use/ignore/force Index
• 告诉优化器要不要用索引，如果是force，即使where里没有索引，也会去用索引。 如果是ignore，则就是不用，傲娇
• optimizer_search_depth
  dfs搜索计划时的最大深度
• optimizer_prune_level
  根据扫描的行数来决定是否跳过执行计划？
• optimizer_switch
  选择是否关闭某些优化器特性

[toc]

mysql执行查询的过程#

1. 客户端先发送查询语句给服务器
2. 服务器检查缓存，如果存在则返回
3. 进行sql解析，生成解析树，再预处理，生成第二个解析树，最后再经过优化器，生成真正的执行计划
4. 根据执行计划，调用存储引擎的API来执行查询
5. 将结果返回给客户端。

下面是详解

一、客户端发查询请求到服务端之间的原理#

• 客户端和服务端之间是半双工的， 即一个通道内只能一个在发一个接收， 不能同时互相发互相接收
• 客户端只会发送一个数据包给服务端，并不会在应用层拆成2个数据包去发（max_allowed_packet可以设置数据包最大长）， 这关系到sql语句不能太长。
• 服务端返回给客户端可以有多个数据包， 但是客户端必须完整接收，不能接到一半停掉连接或用连接去做其他事（UI界面可以操作，不同的线程）
• 例如java，如果没设置fetchSize，那么都是一次性把结果读进内存。当你使用resultSet的时候，其实已经全部进来了，而不是一条条从服务端获取。————使用fetch Size边读边处理的坏处： 服务端占用的资源时间变久了。

查询mysql服务此时的状态：

使用 show full processlist 命令可以查看mysql服务端某些线程的状态

• Sleep 正在等待客户端发送新的请求
• Query 正在执行查询， 或者发结果发给客户端
• Locked 正在等待表锁（注意表锁是服务器层的， 而行锁是存储引擎层的，行锁时状态为query）
• Analyzing and statistics 正在生成查询的计划或者收集统计信息
• copying to tmp table 临时表操作，一般是正在做group by等操作
• sorting result 正在对结果集做排序
• sending data 正在服务器线程之间传数据

二、优先查询缓存#

• 缓存的查询在sql解析之前进行。
• 缓存的查找通过一个 对大小写敏感的哈希表实现，即直接比对sql字符串。
• 因此只要有一个字节不同，都不会匹配中。（毕竟还没开始解析，大小写什么的他也不知道要不要区分）
• 第7章中有更详细的查询缓存。

三、查询前做语句优化处理#

1.语法解析器和预处理#

• 这里就是把sql做解析， 变成一个解析树。解析时会做mysql语法规则验证。
• 语法解析器: 检查关键字错误、关键字顺序、引号匹配
• 预处理：和元数据关联校验， 检查数据表和列是否存在，解析名字和别名。
• 权限校验

2.查询优化器(重点）#

• mysql可能会生成多种计划， 他会分别计算一个预测成本值，然后选一个成本最小的计划
• 计算信息来自于 表的页面个数、索引分布、长度、个数、数据行长度
• 因为多种原因，可能不会选择到最优的计划，有偏差
• 静态优化和动态优化的区别：
  静态优化类似“编译期优化”，只和语句结构有关，和具体值无关
  动态优化是在运行中去优化的，需要依赖索引行数、where取值，执行次数可能比静态优化要多。

mysql的优化类型#

• 关联表（join）的顺序可能会变
• outer join可能会变成内连接
• 优化条件表达式， 例如 5=5 AND a>5被简化成a>5
• 优化MAX\MIN， 如果是MAX(索引），那么直接拿B+树的第一条或者最后一条即可。
• 当发现某个查询或者表达式的结果是可以提前计算出来的时候，就会优化成常数
• 索引覆盖，如果只要返回索引列，就不会走到最底层去。
• 子查询优化
• 提前终止查询（例如LIMIT）
• 等值传播： join中可能把左表的where 拿给右表一起用
• IN(1,2,3,4,5,6)这个条件， 并不是简单遍历判断， 会先排序，然后用二分去判断是否存在。

3.数据和索引的统计信息#

• 统计信息是存储引擎去计算的，不同的存储引擎有不同的统计信息
• 服务器层生成查询计划时，会向存储引擎获取这些信息。

4.MYSQL对关联查询的执行#

• join查询的本质其实是读取临时表做关联
• 例如a inner join b on a.id=b.id where a.xx=y

1. 遍历a的每一行（此时a表本质上是 select * from a where a.xx=y）
2. 在那行中a的id被定下来， 那么就会去获取一个临时表，临时表为（select * from b where a.id = id）
3. 接着用这个临时表和a那一行拼接，输出多行。
4. 然后再用这里的结果作为临时表，给更上层的关联去用（嵌套查询的含义）。

• 如果是left join，则就是临时表如果为空，则给a那一行拼接一个null。

5. 执行树优化#

6. 关联查询优化器#

• join实际执行的顺序会关系到性能
• 例如a\b\c三个表关联， 可能先让a和b关联得到的临时表里的记录只有10条， 而如果让a和c先关联，会有10000条， 那么后面的效率就会截然不同
• EXPLAIN EXTENDED可以展示关联的顺序
• STRAIGHT_JOIN可以手动指定关联顺序
• mysql自己会评估搜索一个最优的顺序， 但如果join表太多，则无法搜完所有结果（O(n!))， 那时候就会采用贪心。 是否使用贪心算法的边界值可以根据optimizer_seartch_depth去指定。

7.排序优化#

• 如果排序的量小，就用内存快速排序；如果排序的量大，就用文件排序
• mysql有2种取排序数据的方式：

1. 两次传输排序： 先取要排序的字段加行序号，按照字段排序好之后，再根据行索引一条条取读
   优点: 排序时占用内存小。
   缺点: 排序之后读的过程会很慢，根据行序号取读不是很方便
2. 单次传输排序： 直接把行读出来（行里只有需要用的列，不一定是整行） ，然后排序
   优点: 把全部行读出来相当于顺序IO，读取速度快
   缺点: 可能会很大导致需要文件排序

• 关联查询order by的注意事项
  如果order by的列 都 来自关联的 第一张 表，则直接第一张表join的时候就排序了。
  除此之外！！ 都是全部join完，再排序！ 就算用了limit，也是全部join+排序后， 再limit的！

四、真正执行查询计划#

• 执行计划是一个数据结构

五、返回结果给客户端#

• 用tcp封包并逐步传送，而不是全部准备好再发送。

[toc]

垂直分表#

Q： 什么是垂直分表？ 一般怎么分的？#

A:
将一个表按照字段分成多表，每个表存储其中一部分字段。
垂直分表原则：

• 把不常用的字段单独放在一张表;
• 把text，blob等大字段拆分出来放在附表中;
• 经常组合查询的列放在一张表中;

Q: 什么情况下需要分表， 提升是什么？#

当有些字段内容比较大，且访问频次比较低时， 可能会导致表的大小非常大，但是用途很小。
例如 商品信息表里， 商品详情表可能字段更多文字也更多，倾向于将详情表单独拆一个出来。 这样业务层可以在真正需要用到详情表的时候，再根据商品id去查就行了。

提升：
1.为了避免IO争抢并减少锁表的几率，查看详情的用户与商品信息浏览互不影响
2.充分发挥热门数据的操作效率，商品信息的操作的高效率不会被商品描述的低效率所拖累。

Q ： 为什么大字段的效率低呢？#

A：

1. 由于数据量本身大，读取整行记录需要更长的读取时间；
2. 跨页，页是数据库存储单位，很多查找及定位操作都是以页为单位，单页内的数据行越多数据库整体性能越好。而大字段占用空间大，单页内存储行数少，因此IO效率较低。
3. 数据库以行为单位将数据加载到内存中，这样表中字段长度较短且访问频率较高，内存能加载更多的数据，命中率更高，减少了磁盘IO，从而提升了数据库性能。

水平分表#

水平分表是在同一个数据库内，把同一个表的数据按一定规则拆到多个表中。
以商品表为例：
商品信息及商品描述被分成了两套表。

• 如果商品ID为双数，将此操作映射至商品信息1表；
• 如果商品ID为单数，将操作映射至商品信息2表。此操作要访问表名称的表达式为商品信息[商品ID%2 + 1]

Q: 垂直分表和水平分表的区别？#

A:
垂直分表，是对字段列做划分。 而水平分表，是对数据行做划分。
其实可以把表成下面这种结构，就明白垂直和水平的区别了

Q: 水平分表的好处？#

A:

• 优化单一表数据量过大而产生的性能问题
• 避免IO争抢并减少锁表的几率

库内的水平分表，解决了单一表数据量过大的问题，分出来的小表中只包含一部分数据，从而使得单个表的数据量变小，提高检索性能。

垂直分库#

和垂直分表类似， 只不过根据业务类型，将不同业务的表放到的不同的数据库

垂直分库是指按照业务将表进行分类，分布到不同的数据库上面，每个库可以放在不同的服务器上，它的核心理念是专库专用

Q: 已经做了垂直分表了，为什么还要垂直分库？#

A:
通过垂直分表性能得到了一定程度的提升，但是还没有达到要求， 当两类表的数据量持续增加时，磁盘空间肯定会不够，毕竟数据还是始终限制在一台服务器（例如用户和商品持续增长）。

即库内垂直分表只解决了单一表数据量过大的问题，但没有将表分布到不同的服务器上，因此每个表还是竞争同一个物理机的CPU、内存、网络IO、磁盘。

Q: 垂直分库的好处#

A:

• 解决业务层面的耦合，业务清晰
• 能对不同业务的数据进行分级管理、维护、监控、扩展等
• 高并发场景下，垂直分库一定程度的提升IO、数据库连接数、降低单机硬件资源的瓶颈
• 垂直分库通过将表按业务分类，然后分布在不同数据库，并且可以将这些数据库部署在不同服务器上，从而达到多个服务器共同分摊压力的效果，但是依然没有解决单表数据量过大的问题。

水平分库#

当业务上无法再进行垂直拆分时，但是库的容量不够时，就只能水平分库了。

水平分库是把同一个表的数据按一定规则拆到不同的数据库中，每个库可以放在不同的服务器上，但是不影响表结构

• 例子：
  操作某条数据，先分析这条数据所属的店铺ID。如果店铺ID为双数，将此操作映射至RRODUCT_DB1(商品库1)；如果店铺ID为单数，将操作映射至RRODUCT_DB2(商品库2)。此操作要访问数据库名称的表达式为RRODUCT_DB[店铺ID%2 + 1]

好处：

• 解决了单库大数据，高并发的性能瓶颈。
• 提高了系统的稳定性及可用性。

Q: 如果水平分库后，又不够用了，数据要做迁移吗？即怎么做平滑扩展#

A:
水平分库如何做到平滑扩展

1. 停服迁移。
   适用于特定时间段用户几乎无法登录或者操作的产品，或者有权限控制用户不允许使用的。
2. 从库升级。
   可以理解为原本作为容灾的从库， 直接升级为可以被哈希映射的主库， 加入到水平分库的哈希映射中。
   
3. 双写迁移
   用于未设置从库，或者必须新增更多的库时（从库一次只能*2）。

1. 设置新的分片库，要求库内为空。 同时记录一下当前时间或者当前记录号。
2. 业务层增加逻辑，将相同哈希的数据多写一份到新库（注意此时新库只能被写，但是不能被读）
3. 将老记录通过工具迁移到新库，尽量全部迁移
4. 迁移完成后，校验，确保两边已经完全一致(其实类似于生成了一个从库）
5. 开放新的分片规则。 去除冗余数据。
   

Q: 从库迁移中， 从库中有之前备份的数据，怎么办？#

A:
备份数据不影响使用，只要哈希正确，冗余数据不会干扰。
但可以安排一个特定时间进行冗余数据清理， 且清理过程不会影响自己所映射的数据一致性。

Q: 一致性哈希有了解吗？ 和水平分库有什么关系？#

A:
如果是简单哈希， 上面提到的扩容中，可能一次变动就要所有的库都涉及迁移。
但我可能只想增加一台呢？ 也要全部都变动吗？

为了尽可能少迁移，只迁移1-2个库，引入一致性哈希。 这样只要改动哈希空间中相邻的即可
具体原理这里有提到服务缓存设计

分库分表设计问题#

Q: 分库分表会带来什么负面影响？#

A:

• 无法使用部分外键约束
• 多表join连接的sql查询，可能需要改造成多次单表查询（注意，分库分表场景下，尽量都用多次单表查询，可读性提高， 牺牲少数性能而已）
• 无法继续使用数据库自身提供的方法生成全局唯一id。

Q: 那你的产品要引入分库分表的话， 怎么实现？ 自己写代码吗？#

A:
不需要，有完善的分库分表中间件。
Shark、mycat、tddl。

以shark为例 ， shark依赖于spring， 只需要通过依赖注入方式配置shark的各种属性、分库分表路由算法，即可使用
业务层调用dao的代码不需要任何变化。
基于AOP拦截jdbcTemplate中除了batch()方法以外的所有读/写方法
利用druid的sqlparse完成sql语句的解析工作。

Q: 分库分表之后， 全局且连续的唯一id如何生成？#

A:
如果不考虑连续， 则生成时结合uuid、机器ip、时间戳等多个维度因素生成即可。
如果要考虑连续，有两种方式

1. 利用分表中间件的id生成器， 例如shark，可以配置一个单点id数据库， 需要id时， 应用里的shark会去这个id数据库申请一批id， 缓存在本地。
   利用了行锁保证了并发环境下的数据一致性。
2. 建立一个id生成服务， 需要的时候走这个单点服务去申请（单点服务自身有个mysql），代价比较大。

Q: 分库分表之后， 可能一个表被拆成多个表， 但是原先某个业务查询sql涉及了其中的多个条件， 搜索变得非常慢，应该怎么处理？#

A:
可以把数据导入到solr中， 让solr进行分词搜索。
另外如果有比较耗时的like查询，也可以导入给solr让solr做like模糊查询。

Q: 垂直分表后， 可能会产生 冗余表， 即分成卖家表和买家表后， 他们表里都需要订单信息， 因此订单信息需要同步2次给2个表。 这个过程你会如何设计？#

A:

1. 自己在业务层实现双写逻辑。 订单服务写入买家表之前， 把卖家表的请求扔给异步消息队列， 这样就是一边异步一边同步，加快速度。
   而卖家表如果插入成功了， 就再发一个响应消息给消息队列， 订单服务消费到这个响应后，才能确认写入成功，短时间内收不到则就进行数据补偿类似于重发。 （也叫线上检测补偿）

2. 借助某些已经实现的中间件做mysql数据库的binlog增量同步。（阿里的canal）。
   它会伪装salve节点，向master节点索要binlog， 然后解析binlog后，完成冗余表的数据增量同步，就不需要业务层写代码了，配置canal中间件即可。

Q: 大表怎么分页查询？#

A:
给时间加索引，然后利用offset+limit即可
select * from t_msg order by time offset 200 limit 100

Q: 分库分表后，怎么做分页查询？#

以offset 900 limit 60， 3个库为例
A:
4种方法。

1. 全局视野法
   用于数据量不大的情况
   每次直接取limit 960， 然后在服务端进行排序后手动算出offset 900的位置。

2. 禁止跳页。
   只提供下一页。这也可以用全局视野拿到第一页后， 记录此时选到的时间。
   下一页的时候， 用3个库里记录的那个时间做排序再去取第二页即可。

3. 模糊查询
   当数据获取要求的精确度不高，且数据确定是均匀分布的
   则直接按offset 300 limit 20去取3份合成一页即可。

4. 二次查询法
   比较复杂。

• ① 先分别offset 300 limit 60， 得到3份数据。
• ② 得到3份数据中的最小时间tmin， 这个时间的前面300份是可以被“肯定的”
• ③ 记录另外2个库（就是没取到最小时间的那2个）的时间最大值tmax1, tmax2
• ④ 按 time>tmin and time < tmax1 和 time>tmin and time<tmax2 的where索引查询再取2份数据。
• ⑤ 这也就能知道tmin 在3个库里的相对位置是多少了， 例如在库1里排300名，在库2里排250名， 在库3里排270名。
• ⑥ timin排820名，而刚才取的数据合并起来后，再取个80条，就能找到limit 900的位置了。
  也有缺点， 就是极端情况下还是不太好用，例如库2和库3的分布机器不均匀。
  业界难题-“跨库分页”的四种方案

彻底搞清分库分表（垂直分库，垂直分表，水平分库，水平分表）

[toc]

数据库日志分类#

Q: 数据库有哪三种log？#

A:

• redo log
  和大多数关系型数据库一样，InnoDB记录了对数据文件的物理更改，并保证总是日志先行，也就是所谓的WAL
  即在持久化数据文件前，保证之前的redo日志已经写到磁盘。
  mysql重新启动时会检查redo log的日志，把由于mysql异常退出导致没有刷新到磁盘的数据页从redo log中恢复。
  innodb_log_group_home_dir表示redo log的目录；innodb_log_file_size表示redo log文件的大小；innodb_log_files_in_group表示redo log文件个数。
  redo log文件以ib_logfile[number]命名。

• undo log
  为了满足事务的原子性，在操作任何数据之前，首先将数据备份到一个地方（这个存储数据备份的地方就是undo Log）。然后进行数据的修改。如果出现了错误或者用户执行了ROLLBACK语句，系统可以利用undo Log中的备份将数据恢复到事务开始之前的状态。
  详细分析MySQL事务日志(redo log和undo log)

• bin log(二进制日志）
  记录sql语句，可用于主从复制。
  二进制日志只在事务提交的时候一次性写入(基于事务的innodb二进制日志)，提交前的每个二进制日志记录都先cache，提交时写入
  [查询日志、二进制日志详解](https://www.cnblogs.com/f-ck-need-u/p/9001061.html

Q: binlog和relog都有哪些区别呢？#

A:

1. 层次不同。
   bin二进制日志是在存储引擎的上层产生的，不管是什么存储引擎，对数据库进行了修改都会产生二进制日志。而redo log是innodb层产生的，只记录该存储引擎中表的修改
2. 记录的东西不同。
   二进制日志记录操作的方法是逻辑性的语句。本质也还是逻辑的SQL设置，如该行记录的每列的值是多少。而redo log是在物理格式上的日志，它记录的是数据库中具体到每个页的修改。
3. 写日志的时机不同。
   二进制日志只在每次事务提交的时候一次性写入缓存中的日志"文件"(对于非事务表的操作，则是每次执行语句成功后就直接写入)。
   而redo log在数据准备修改前写入缓存中的redo log中，然后才对缓存中的数据执行修改操作
4. 一次事务生成的日志记录数不同。
   二进制日志一次提交对应一次记录。
   而redo log中是记录的物理页的修改，redo log文件中同一个事务可能多次记录，最后一个提交的事务记录会覆盖所有未提交的事务记录。

例如事务T1，可能在redo log中记录了 T1-1,T1-2,T1-3，T1* 共4个操作，其中 T1* 表示最后提交时的日志记录，所以对应的数据页最终状态是 T1* 对应的操作结果

5. 幂等性不同
   二进制日志不具有幂等性。重复执行多次会造成数据错误。
   redolog具有幂等性， 因为始终是对页做覆盖，不会出错

relog#

relog刷磁盘时，存在应用层logBuffer、 操作系统层面的buffer、日志文件。

Q: relog刷日志到磁盘有哪几种方式？#

A:
MySQL支持用户自定义在commit时如何将log buffer中的日志刷log file中。这种控制通过变量 innodb_flush_log_at_trx_commit 的值来决定。该变量有3种值：0、1、2，默认为1

• 当设置为1的时候，事务每次提交都会将log buffer中的日志写入os buffer并调用fsync()刷到log file on disk中。。
• 当设置为0的时候，事务提交时不会将log buffer中日志写入到os buffer，而是每秒写入os buffer并调用fsync()写入到log file on disk中。也就是说设置为0时是(大约)每秒刷新写入到磁盘中的，当系统崩溃，会丢失1秒钟的数据。
• 当设置为2的时候，每次提交都写入到os buffer，并且是每秒调用fsync()将os buffer中的日志写入到log file on disk。
  

Q: relog日志块的格式是怎么样的？#

A:

• redo log以块为单位进行存储的，每个块占512字节，这称为redo log block。（不管是log buffer中还是os buffer中以及redo log file on disk中，都是这样以512字节的块存储的）
• 组成部分：

1. 日志块头（包含buffer中的位置id、已记录log大小、涉及分拆日志块时的偏移位置、检查点信息）
2. 日志块尾
3. 日志主体
   

有时候一个数据页产生的日志量超出了一个日志块，这是需要用多个日志块来记录该页的相关日志。例如，某一数据页产生了552字节的日志量，那么需要占用两个日志块，第一个日志块占用492字节，第二个日志块需要占用60个字节，那么对于第二个日志块来说，它的第一个log的开始位置就是73字节(60+12)

binlog#

Q: binlog的格式又是怎么样的？#

A:
mysql binlog日志有三种格式，分别为Statement,MiXED,以及ROW！
可以用命令查看自己的mysql用的是什么模式。

• statement 只记录更新的sql语句
  缺点：
  像一些特定函数功能，slave可与master上要保持一致会有很多相关问题(如sleep()函数， last_insert_id()，以及user-defined functions(udf)会出现问题

• Row:不记录sql语句上下文相关信息，仅保存哪条记录被修改，仅需要记录那一条记录被修改成什么了。
  一条update语句，修改多条记录，则binlog中每一条修改都会有记录，这样造成binlog日志量会很大

• Mixedlevel：以上两种level的混合使用。MySQL会根据执行的每一条具体的sql语句来区分对待记录的日志形式，也就是在Statement和Row之间选择一种

Mysql默认是使用Statement日志格式，推荐使用MIXED.

undolog#

Q: undolog的日志格式？#

A:
对数据的变更操作，主要来自 INSERT UPDATE DELETE，而UNDO LOG中分为两种类型
一种是 INSERT_UNDO（INSERT操作），记录插入的唯一键值；
一种是 UPDATE_UNDO（包含UPDATE及DELETE操作），记录修改的唯一键值以及old column记录。
因此update/delete操作的undolog数据会比insert操作的数据多

Q: checkpoint是做什么的？#

A:
“检查点”会创建一个已知的正常点，在意外关闭或崩溃后进行恢复的过程中， SQL Server 数据库引擎 可以从该点开始应用日志中所包含的更改。
检查点（Checkpoint）的本质

Q: LSN称为日志的逻辑序列号, 具体是怎么生效的？#

A:

[toc]

第一题:栈的应用#

面试题 03.04. 化栈为队 - 力扣（LeetCode）

要出队或者要用到队头的时候，移动到另一个栈里，就能反向取了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class MyQueue {
    Deque<Integer> q1 = new LinkedList<>();
    Deque<Integer> q2 = new LinkedList<>();
    /** Initialize your data structure here. */
    public MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        q1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!q2.isEmpty()) {
            return q2.pop();
        }
        while(!q1.isEmpty()) {
            q2.push(q1.pop());
        }
        return q2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if (!q2.isEmpty()) {
            return q2.peek();
        }
        while(!q1.isEmpty()) {
            q2.push(q1.pop());
        }
        return q2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

第二题:bfs#

733. 图像渲染 - 力扣（LeetCode）

一个简单题，我用bfs写了半天，确实累，是不是应该搞点bfs的模板了？下次比赛直接用上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    int[][] dirs = new int[][]{{1,0},{-1,0}, {0,1}, {0,-1}};
    
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        Queue<int[]> queue = new LinkedList<>();
        int ylen = image.length;
        int xlen = image[0].length;
        boolean[][] vis = new boolean[ylen][xlen];
        queue.offer(new int[]{sr,sc});
        vis[sr][sc] = true;
        int startColor = image[sr][sc];
        image[sr][sc] = color;
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            int y = p[0];
            int x = p[1];
            for (int[] dir : dirs) {
                int ny = dir[0] + y;
                int nx = dir[1] + x;
                if (nx < 0 || ny < 0 || nx >= xlen || ny >= ylen || vis[ny][nx]) {
                    continue;
                }
                if (startColor != image[ny][nx]) {
                    continue;
                }
                vis[ny][nx]= true;
                image[ny][nx] = color;
                queue.offer(new int[]{ny, nx});
            }
        }
        return image;
    }
}

第三题:哈希表以及数据范围确认习惯#

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

看起来很简单，直接一个数组搞定

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public boolean isUnique(String astr) {
        boolean[] vis = new boolean[26];
        for (char c: astr.toCharArray()) {
            if (vis[c-'a']) {
                return false;
            }
            vis[c-'a'] = true;
        }
        return true;
    }
}

但这题究竟想考察什么呢？ 看一下下面这段话：

如果我是面试官，会考虑主要考察什么，就我的工作经验看，大多数主要是招聘工程师的，面试者如果什么问题都没有，直接写个二重循环搞定，会首先给个50分，如果能写点判断字符串是否为null的，60分。

直接上手什么bitset，什么位运算的，我会先问他，题目中有没有交代字符串的字符一定是26个英文字母？如果是unicode环境，你是不是要准备2^16/8个字节的空间？在实际项目中，风险可控，结果可期更重要，绝大多数时候不在乎那点时间和资源。

所以我期望面试者不要急于解答，我希望他先问我问题：

1. 字符串的字符范围，如果我告诉他，26个小写英文字母，那可能一开头直接判断如果字符长度>26, 直接返回False，做到这一点的，80分
2. 如果我告诉他ascii字符集，然后他的代码里有边界检查，并且针对不同的范围有不同的侧重点，比如说ascii字符集，那也就是128个可能性，16个字节的位运算比较好
3. 如果我告诉他是unicode，没有字符范围，老老实实排序再判断是比较符合我对工程师的要求的，因为算法性能稳定，没有额外资源要求，一眼看出没什么不可预见的风险，100分。

就是说，有些东西，没想到或者一时没想到根本不是问题，日常工作中稍微提示一下即可，但是缜密的思维对于程序员来说更重要。

[toc]

C（k,n)的O(Min(k,n-k)）解法：#

快速回想组合数解法：
C(8,3) = 8 * 7 * 6 /(321) = 6 / 1 * 7 / 2 * 8 / 3
即分子和分母的个数是一样的
然后你要从小的开始逐步做乘和除的操作，就能求出来了，且一定能保证整除

1
2
3
4
5
6
7
8
9
10

public int c(int k, int n) {
    long result = 1;
    // y/x * (y+1)/(x+1)
    for (int y = k+1, x= 1;y<=n && x<=k;y++,x++) {
        // (result*y)一定能被x整除
        result = (result * y) / x;
    }

    return (int)result;
}

杨辉三角打表法：#

如果空间没要求， 但是要求每次快速获取，则可以用杨辉三角提前打表

1
2
3
4
5

for(int i=0;i<=n;i++){
	c[i][0]=c[i][i]=1;
	for(int j=1;j<i;j++)
		c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

``

如果用O(N)的复杂度，O（1）的空间求解C(n,m)?#

杨辉三角里，某行某列的值等同于C(n,m)

因此可以很短的复杂度得到值
也可以缓存

超大组合数（涉及取余）#

超纲题

• 乘法逆元+快速幂+阶乘
• Lucas定理

总结组合数的几种求法（模板）

相关题目#

62. 不同路径 需要空间为1时，必须用组合数
119. 杨辉三角 II O(1)空间求某行某列，用组合数性质

[toc]

索引的基本概念#

索引的优点#

1. 大大减少服务器需要扫描的数据量（本来O(n)的扫描，在B-Tree或者哈希索引的帮助下， 变成O(logn)或者O(1)）
2. 避免了不必要的排序或者临时表（order by和排序需要先弄一个临时存储的表）
3. 把随机IO改成为了顺序IO，IO速度加快

索引类型#

• 支持的类型

1. 全值匹配——key中所有索引列全部匹配中，单个的
2. 匹配最左索引——匹配key中的第一个索引值
3. 匹配列前缀——可以只匹配某个索引的前缀（适用于字符串的情况）
4. 可以匹配最左索引+列前缀——可以只匹配 索引1、索引2加上索引3的前缀。

• 注意上面的匹配，都是从左往右的匹配， 因此不支持只匹配中间那个索引的情况。
• 如果有一列索引用了范围， 那么后面的列都不能再用来匹配了。
• B-Tree也可用于排序或者group by key，会加快速度，毕竟默认都是排好序的了。

哈希索引#

• 指的是把 索引列计算出一个哈希值， 存到一个哈希表中， key是哈希值，val是行指针。
• 只有Memory引擎支持（key using hash(索引值） ）， inndb不支持。
• 因为不是按照顺序存的， 所以不可用于优化排序， 只能优化查询。
• 不支持部分索引匹配， 因为哈希值是根据全索引计算的。
• 也不支持范围。
• 如果有哈希冲突，且很多，就可能造成性能变慢，

自定义哈希索引#

• 可以利用B-tree弄一个自定义的哈希索引
• 例如想哈希的列是url， 于是我弄了一个hash_url的列, 里面的值是url经过CRC32(url）后的值， 然后把hash_url这一列作为索引。
• 然后select语句的时候， where url = ‘xx’ and hash_url=CRC32(‘xx’) ，即可 快速定位。
• hash_url的值可以通过insert触发器，每次插入url的时候进行更新
• 查询时必须带上哈希前原本的值（就是上面的url = ‘xxx’)，否则可能会因为哈希冲突返回多行。
• 不可用SHA1和MDK做哈希函数。

空间数据索引（R-Tree)#

• 只有MyISAM才支持
• 从所有维度来索引数据，用于地理信息存储之类的

全文索引#

• 查找文本中的关键词
• 可以同时创建全文索引和基于值的B-Tree索引

三星索引的评价#

• 一星：需要拿的记录都放到同一行（即不用再关联其他表）
• 二星：索引数据顺序和查找顺序一致
• 三星: 索引的列包含了查询中需要的全部的列（即不用去返回行中所有顺序，直接返回key就好了）

索引原理#

B+ tree实现#

• 如果没有指明类型，基本上都是用的B+ tree索引
• B+ tree结构

里面的key就是 你选定的索引值
然后按照范围，指向后面其他的范围，直到定位到具体的叶子节点即行所对应的值。
同时因为最后叶子都是按照顺序连起来的，所以也很适合按照范围返回数据。

• B+tree里的key可以包含多个列的值， 并且这些列匹配时有顺序关系，按照定义key时的优先级来排序。（就是说可以多个key组成一个节点，里面自定义了对应的判定顺序）
  

Q: 为什么不选择使用B树， 而是使用B+树？#

A:
数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题
正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历
在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作，或者说效率太低。

另外B树的索引节点上也存了数据，导致搜索过程种读了很多不必要的数据，加大了磁盘IO时间

Q: 那为什么不选用红黑树？#

A:
红黑树往往出现由于树的深度过大。
磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写

Q: 那为什么不用哈希表？#

A:
哈希表没法做范围查询以及前缀索引匹配查询。

高性能的索引策略#

独立的列的问题#

• 索引列不可以作为表达式的一部分， 必须是独立的
  例如 where id+1=5 或者 where Func(id) < 5 都是错误的
  应该改成
  where id = 5-1 或者 where id < uFunc(5)

前缀索引优化#

• 索引列如果是text之类特别长的，必须使用前缀索引， 不可以用完整长度去做索引，mysql不支持。

前缀索引的创建#

… KEY(city(7)), 那么你按照city去where时，就会用city的前缀去索引了。

确定前缀长度#

• 前缀索引的选择性 = 不重复的个数/记录总数
• 如何确定较优的前缀长度？

全列选择性：

SELECT COUNT(DISTINCT column_name) / COUNT(*) FROM table_name;

某一长度前缀的选择性：

SELECT COUNT(DISTINCT LEFT(column_name, prefix_length)) / COUNT(*) FROM table_name;

当你不断调整prefix_length，让前缀的选择性越接近全列选择性的时候，索引效果越好。如果发现继续增加prefi_length，变动幅度不大了，则选取那个值

• 也要注意前缀最大值， 例如该长度n下，平均选择性不高，但是有1-2个前缀数量特别大，也不行。

如何做后缀索引？#

存储的时候把字符串 翻转 存进表里，然后再做前缀索引

多列索引#

• 多列索引指的是 多个独立的索引。就是给表定义了Key(a), key(b) ， 而不是Key(a,b)
• 如果在多列索引的情况下，要where a=1 or b= 2， 且要性能好， 需要改成 union(a,b) 即查询union的形式。 mysql5.0之后都会优化成union， 简称 索引合并
• 上述默认优化的缺点: 联合操作会耗费大量的CPU和内存。 可是统计时间时又不会统计进来，导致低估时间成本。
• 可以通过explanin sql语句， 查看extra中是否有using union(a,b)来判断是否有索引合并的情况

如何确定索引列顺序#

• 这里指的是如何确定key(a,b,c)里abc的顺序
• 通用法则：把选择性最高的那个列放前面
• 选择性计算： distinct(列)/count(*) 越大，选择性越好。
• 因为这样的话，可以减少在叶子节点上的遍历。
• 特殊情况： 某场景下突然表里的username都变成了一样的用户名， 然后对username索引做查询时， 就很慢， 因为相当于在叶子节点上遍历去查了，O(n)的复杂度。
• 对于特殊场景，要尽量在数据输入避免， 或者查询避免（例如避免在那个时间段去查询那个统一的username）

聚簇索引#

• 聚簇索引是一种存储结构，而不是索引类型。
• InnoDb默认使用主键列做聚簇索引
• 如果没有主键，则用第一个非空not NULL unique的索引作为聚簇索引
• 如果没主键没索引，则会创建一个隐藏的行id作为聚簇索引（毕竟他总要搞一个B+树)

聚簇和非聚簇的区别#

• 聚簇索引其实就是指，当你搜索到B+树的叶子之后， 叶子里存的就是数据行了，因此叶子的左右都是与自己索引值相邻的数据行，可以串起来直接一起获取。
• 而非聚簇索引时， 当你搜到叶子时， 叶子里依然只有索引值， 而后面的指针才指向真正的位置， 这意味着数据行的存放是不连续的， 没有办法用一根线串起来。

聚簇的优点#

1. 可以一次性读取到 某主键范围的所有行，减少磁盘IO
2. 相比非聚簇，少跑一层（就是最后一层）。

聚簇的缺点#

1. 如果数据都放在内存中，就没优势了，毕竟非聚簇通过指针一样很快。
2. 更新聚簇索引会很慢，因为会重新组织B+树重新移动。
3. B+树插入新行时，可能导致叶子节点的页出现分裂，导致更多的空间。（聚簇索引的叶子非常大！）
   非聚簇的话都是指针，数据不放在叶子中，也就不会出现那种大叶子的分裂。

聚簇和非聚簇的对比#

Innodb都是聚簇索引，叶子节点一般就是数据，数据按顺序存储了。
MyIsam都是非聚簇索引， 叶子节点还是索引，凌乱指向存储位置。

Q: 什么是回表？#

A:
非聚簇索引查询时， 因为最终只查到的是主键值，最终还需要经过聚簇索引找到数据行

如粉红色路径，需要扫码两遍索引树：

1. 先通过普通索引定位到主键值id=5；
2. 在通过聚集索引定位到行记录；
   这就是所谓的回表查询，先定位主键值，再定位行记录，它的性能较扫一遍索引树更低

Q: 那么当发生回表时，怎么避免呢？#

A:
把普通索引列升级到联合主键中。
例如将单列索引(name)升级为联合索引(name, sex)，即可避免回表(代价是name要放到第一个，或者sex in ‘男，女’）

Q: 非主键索引a， 做where a>3时， 能充分利用索引做简单的范围读取么？#

A:
不能。
因为非主键索引最终还是要做回表， 到主键（聚簇）索引树中进行查询。此时a>3是无法直接取出一堆数据的。

mysql5.5之前， 是每个a>3的记录都进行随机回表读取数据。
mysql5.5之后，做了一个MR2优化

1. 当a>3的记录不是很多时， 会读取到内存中
2. 接着按照主键id（聚簇索引）进行排序
3. 然后根据id排序后的情况进行回表， 如果有一堆id都是挤在一起的，就对这一批id进行范围查询。

二级索引和主键#

• 注意， 如果有1个key(xx)加一个primKey(yy)， 相当于有2个索引（主键默认索引）
  而这2个索引的意思是指：
  建立了2个B+树！！
  对于主键的B+树， 数据就放在叶子
  而对于另一个索引的B+树， 叶子节点是主键+索引， 后面才是指向数据
• 即对于聚簇索引，如果存在主键和二级索引，则选择主键做聚簇， 二级索引和非聚簇索引的B+树没两样。

Q: 主键索引和唯一索引有什么区别呢？#

A:

1. 主键索引一定是唯一索引， 但唯一索引不一定是主键。
2. 主键索引列默认不支持空值， 而唯一索引本身没有这个限制。
3. 主键产生唯一的聚集索引（即聚集索引和主键相关），非主键唯一索引产生唯一的非聚集索引
4. 唯一索引可以有多个， 但是主键只能有一个。

Q: 确定不能有多个主键索引吗？那泛式里提到的多个主键是怎么回事呢？#

A:

1. 数据库的每张表只能有一个主键，不可能有多个主键。

2. 所谓的一张表多个主键，我们称之为联合主键。

注：联合主键：就是用多个字段一起作为一张表的主键。

3. 主键的主键的作用是保证数据的唯一性和完整性，同时通过主键检索表能够增加检索速度。

索引的插入#

索引插入的规范#

• 尽量保证在插入时是按索引的顺序插入的
• 如果没按顺序插入，会导致经常性的中间分页，移动数据。性能可以差距四倍以上。
• 所以尽量选用自增的id做索引，尽量不要用随机的UUID做大批量插入的操作。
• 如果用了UUID做插入，插入之后还要要用一个命令
  Optimize Table 表名
  来重建表并优化页的填充
• 什么时候顺序主键的插入是不好的？
  同一时刻并发插入（非单线程插入）的情况
  这会导致在 数据表末尾发生激烈的竞争冲突（如果是随机的反而可以避免这个情况） P171

Q: 为什么自增id可能会出现不连续的情况？#

A:
插入时，如果insert语句中不包含id，但是id设成了自增
mysql此时就会从某个自增表中申请一个主键，当申请成功之后，就会拿着这个主键+1去做真实的Insert操作。（注意，是先申请，再插入）
如果主键/唯一键冲突，或者事务回滚， 这个自增id不会回滚。 下一次会继续主键+1使用。
因此

Q: 为什么自增id不能回滚呢？#

A:
为什么不回退，是避免回退导致重复的冲突，也为了避免太大范围的锁

• 避免回退导致多个id同时插入引发重复的冲突，也为了避免太大范围的锁
• 自增主键比较大的作用是避免页分割，我们只需要数据是递增而无需连续

其他索引#

覆盖索引#

指查询语句中 只有索引相关的列。

• 这样的话，可以不需要回表访问聚簇索引树了， 直接拿索引节点里的索引结果返回，效率非常高。
• 全覆盖的情况比较少见，一般用于
  先用覆盖索引的查询语句得到一个小表
  再利用这个小表的结果对原表做查询（相当于省去了一些条件里的判断）
• Explanin 解析时，如果extra显示 using index，则说明使用了覆盖索引。

用索引做排序#

• 索引和排序语句写对的话，可以不需要弄临时表做排序，直接按照顺序取出返回即可。
• 索引列的顺序， 必须和order by中声明的索引顺序一致
• 即你的key是(a,b,c)， 那么oder by a b c才行，不能打乱顺序
• order by 索引满足 前缀定理， 即必须是 a 或者 a+b或者 a+b前缀
• 特例： 如果where中定义了a=‘某个常量’， 那么order by中只需要b和c也满足 前缀定义。
• 如果是范围就不行了

压缩（前缀索引）#

• 就是把索引在存储的做压缩，减少字节数
• 例如第一个索引是perform， 第二个是performance， 那么第二个存储的时候就表示为7,ance
• 可以在Create Table语句中指定PACK_KEYS来控制索引压缩
• 压缩索引主要是为了减少磁盘和内存占用量， 但因为压缩了，每次到节点时要先解开压缩再计算（即只有用到才解压），再去查找，会降低性能。

重复索引#

primary key、 unique(key)、 index(key）这3个本质上都会形成索引，很容易有人定义了主键后， 又给主键加个索引， 这就会出现多个相同的B+树。

冗余索引#

• 创建了索引（A，B）之后， 又创建了（A）， 那么就是冗余， 因为（A，B） 可以实现单独A的索引功能。
• 所以尽量修改索引，而不是去新增索引， 新增索引容易出现冗余索引。
• 修改索引的缺陷: 可能导致一些老的查询语句的性能下降。
  例如本来是用索引（A） + 主键ID排序做查询， 那个脚本一直在跑很正常， 后来改成了索引（A.B） + 主键ID排序， 于是原先的脚本性能GG， 因为A和ID被B分开了（只是我们看不到ID放在我们定义的key里）

未使用的索引#

• 就是定义了但是平时不用的索引！
• 定位未使用索引的方法： 打开userstates变量， 然后让服务器运行几天之后， 查询INFORMATION_SCHEMA.INDEX_STATISTICS用来查看索引的使用频率。
• 具体见P188

索引和锁#

• 索引能够减少访问的行数，从而减少锁的数量

索引应用#

多种过滤条件优化#

• 如果我们的索引是 sex country age， 但是我们的查询里不关心sex，怎么办？ 如果不走sex，索引就失效了
  可以在where中加入 sex in (‘m’,‘f’) 这样就能用到sex了
• 原则1：
  枚举少的放前面， 这样可以用in方式来处理
• 原则2：
  经常范围性查询的索引列放后面 ，例如age， 毕竟范围查的话，后面的索引就肯定用不了了。

避免多个范围条件#

• mysql会把in(1,2,3)和 >1 and < 3 都认为是range的type， 不过在索引的使用， in之后还可以接其他索引， 但是大于1小于3就不行了
• 如果出现了 lastoneline > xxx and age between x and y
  这种2个范围的索引查询，就会导致age索引失效
• 一种优化的办法： 如果lastoneline > xxx 仅仅是表示 这个用户是否未过期，则可以新增一个经常维护的字段active，来吧lasttime>xxx的这个条件转成true和false这两种值。
• 那么后面就可以改成lastline = true and age between… 了， 用等值的话，就不会影响后面的索引

Q: 写入表的时候， 为什么一般建议自增的主键id来写入？#

A:
因为底层的索引本质上是B+树
有页分裂
如果id随机，则写入时会碎片化，无法做到顺序写

本期总结：#

1. N种东西组成最大字典序回文时，先把成双的都处理掉，每组留下1个或者0个， 最后再考虑怎么拼接这些
2. 子序列和第K个，可以考虑从最小数字开始， 每次保留当前数字，选下一个数字， 或者废弃当前数字，选下一个数字， 并都放入堆中， 这样每次可更新得到最小的子序列。

6152. 赢得比赛需要的最少训练时长 - 力扣（LeetCode）

最开始有点事情，解决完之后发现脑子很乱，这题目其实很简答

对于精力，可以提前算出需要的精力， 而经验可以在每次对战时判断是否要再增加。

但这题就是条件容易看漏，导致错了2次：

需要在经验和精力上都 严格超过对手才能击败他们

严格超过意味着不能等于，导致很多地方得+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int exp = initialExperience;
        int sum = Arrays.stream(energy).sum();
        int res = Math.max(0, sum + 1 - initialEnergy);
        
        for (int i = 0; i < experience.length;i++) {
            if (exp <  experience[i] + 1) {
                res += experience[i] - exp + 1;
                exp = experience[i]+1;
            }
            exp += experience[i];
        }
        return res;
    }
}

6166. 最大回文数字 - 力扣（LeetCode）

这题也搞晕了，实际上很简单。

一堆已知数量的字母要组成回文数， 记住你先把所有成双成对的单独都按拿出来， 剩下的都是1个或者0个字母

然后成双的按大小顺序从外向内组成回文 ， 最后最里面那个单字母的用最大的。

我最开始直接把奇数个数的字母当整体去思考了，其实应该先剔除奇数个数字母中成双的部分，只留下单个的， 最后再去考虑他

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public String largestPalindromic(String num) {
        int[] charCounts = new int[10];
        for (char c : num.toCharArray()) {
            charCounts[c-'0']++;
        }
        int numCount = 0;
        // 最小的字母且是奇数个数的选择放最后
        int endUseChar = -1;
        
        boolean[] oneChar = new boolean[10];
        for (int i = 9; i >=0;i--) {
            oneChar[i] = (charCounts[i] %2 == 1);
            charCounts[i] /= 2;
        }

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for (int i = 9;i>=0;i--) {
            if (i == endUseChar) {
                continue;
            }
            char c = (char)('0' + i);
            int count = charCounts[i];
            if (i == 0 && sb1.length() == 0) {
                continue;
            }
            while (count-->0) {
                sb1.append(c);
                sb2.append(c);
            }
        }
        
        for (int i = 9;i>=0;i--) {
            if (oneChar[i]) {
                sb1.append((char) ('0' + i));
                break;
            }
        }
        
        if (sb1.length() == 0) {
            return "0";
        }
        
        return sb1.append(sb2.reverse()).toString();
    }
}

6154. 感染二叉树需要的总时间 - 力扣（LeetCode）

很容易想到bfs， 先dfs一遍，把每个点的父节点也得到。

然后做bfs即可

另外二叉树的题目中如果涉及map或者set，最好还是直接用引用做key，不容易写错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
        Map<TreeNode,TreeNode> parents = new HashMap<>();
    TreeNode startNode;
    public int amountOfTime(TreeNode root, int start) {
        Queue<TreeNode> queue = new LinkedList<>();
        find(root, null, start);
        queue.offer(startNode);
        Set<TreeNode> vis = new HashSet<>();
        vis.add(startNode);

        int res = 0;
        while (!queue.isEmpty()) {
            // 全部出队
            res++;
            List<TreeNode> nowNodes = new ArrayList<>(queue);
            queue.clear();
            for (TreeNode node : nowNodes) {
                if (node.left != null && !vis.contains(node.left)) {
                    queue.offer(node.left);
                    vis.add(node.left);
                }
                if (node.right != null && !vis.contains(node.right)) {
                    queue.offer(node.right);
                    vis.add(node.right);
                }
                if (parents.get(node) != null && !vis.contains(parents.get(node))) {
                    queue.offer(parents.get(node));
                    vis.add(parents.get(node));

                }
            }
        }
        return res-1;
    }

    void find(TreeNode node, TreeNode parent, int start) {
        if (node == null) {
            return;
        }
        parents.put(node, parent);
        if (node.val == start) {
            startNode = node;
        }

        find(node.left, node, start);
        find(node.right, node, start);
    }
}

6155. 找出数组的第 K 大和 - 力扣（LeetCode）

这题好难，其实知道套路就可以了

我是已经想到先得到 正数的和sum， 然后以这个sum不断减去其他的值，这个减去的就是子序列而且要尽可能小， 同时负数要转整数， 到底是加还是减不需要我们关心。

但是怎么得到第K小的子序列和呢？

答案是用最小堆

先按从小到大排序

然后第0个数字肯定是最小的子序列

接着有2个选择：

① 保留第0个数字， 并继续选取第1个数字

② 废弃第0个数字， 并继续选取第1个数字

这样又得到2个子序列， 最小序列肯定在者2个里面

你会奇怪，者肯定是第②个最小啊？

但是继续走下去

当对于“废弃第0个数字， 并继续选取第1个数字”这个位置，你想废弃第1个数字，选第2个数字时，前面的“保留第0个数字， 并继续选取第1个数字”是可能比它小的， 所以要用堆进行保存，且这样的操作处理时不用考虑任何回溯或者重复的情况！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
   public long kSum(int[] nums, int k) {
        long sum = Arrays.stream(nums).filter(num -> num > 0).mapToLong(num -> Long.valueOf(num)).sum();
        for (int i = 0 ; i < nums.length;i++) {
            nums[i] = Math.abs(nums[i]);
        }
        Arrays.sort(nums);
        // [0]是选择剔除的子序列的和，[1]是当前这个子序列的最右边索引
        // 每次选最小的出来
        Queue<long[]> queue = new PriorityQueue<>((a,b) -> (a[0] > b[0] ? 1 : -1));
        queue.offer(new long[]{0, 0L});
        while (!queue.isEmpty()) {
            long subSum = queue.peek()[0];
            int index = (int)queue.poll()[1];
            if (k == 1) {
                return (sum - subSum);
            }
            k--;
            if (index >= nums.length) {
                continue;
            }
            queue.offer(new long[]{subSum + nums[index], index+1});

            if (index -1 >= 0) {
                queue.offer(new long[]{subSum - nums[index - 1] + nums[index], index + 1});
            }
        }
        return -1;
    }
}