索引的树结构

AI助手支持GPT4.0

查找结构的进化

二分查找

二叉树

二叉平衡树

B-TREE ：二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小

缺点：业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及 CPU 高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。

B+TREE：非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据所在的地址

 

1. B+数据量相同的情况下，非叶子节点可以存放更多的数据，B+树会更加矮胖，io次数会更少

2. B+树有大量的冗余节点（非叶子结点），会让B+树在插入删除时的效率更高

3. B+树的叶子结点用双向链表连了起来，有益于范围查询，而B树只能遍历。

聚簇索引和非聚簇索引

如果叶子节点存储的是实际数据的就是聚簇索引，一个表只能有一个聚簇索引；如果叶子节点存储的不是实际数据，而是主键值则就是二级索引，一个表中可以有多个二级索引。

在使用二级索引进行查找数据时，如果查询的数据能在二级索引找到，那么就是「索引覆盖」操作，如果查询的数据不在二级索引里，就需要先在二级索引找到主键值，需要去聚簇索引中获得数据行，这个过程就叫作「回表」

查询数据的过程

在定位记录所在哪一个页时，也是通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽号），最后在分组内进行遍历查找。

磁盘IO

磁盘处理太慢太慢了

• 尽量减少 I/O 次数，比如可以使用缓存；
• 每次 I/O 尽量获取更多的数据；
• 每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数

总结：

• 数据存储在磁盘（ SSD 跟 CPU 性能也不在一个量级），而磁盘处理数据很慢；
• 提高磁盘性能主要通过减少 I/O 次数，以及单次 I/O 有效数据量；
• 索引通过多阶（一个节点保存多个数据，指向多个子节点）使树的结构更矮胖，从而减少 I/O 次数；
• 索引通过 B+ 树，把业务数据与索引数据分离，来提高单次 I/O 有效数据量，从而减少 I/O 次数；
• 索引通过树数据的有序和「二分查找」（多阶树可以假设为多分查找），大大缩小查询范围；
• 索引针对的是单个字段或部分字段，数据量本身比一条记录的数据量要少的多，这样即使通过扫描的方式查询索引也比扫描数据库表本身快的多；

事务

• 持久性是通过 redo log （重做日志）来保证的；是物理日志，记录做了什么修改
• 原子性是通过 undo log（回滚日志） 来保证的；
• 一致性是binlog保证的 ，逻辑日志（有三种格式）statement，row包含操作的具体数据，mixed
• 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；

死锁问题

处理订单业务时，需要用到select…for update用来避免并发导致的幻读问题，但是这样的话就容易出现死锁

处理方法是破坏形成死锁的条件：打破循环等待条件

• 设置事务等待锁的超时时间。当一个事务的等待时间超过该值后，就对这个事务进行回滚，于是锁就释放了，另一个事务就可以继续执行了。在 InnoDB 中，参数 innodb_lock_wait_timeout 是用来设置超时时间的，默认值时 50 秒。

• 开启主动死锁检测。主动死锁检测在发现死锁后，主动回滚死锁链条中的某一个事务，让其他事务得以继续执行。将参数 innodb_deadlock_detect 设置为 on，表示开启这个逻辑，默认就开启。

关于count

*count(1)、 count()、 count(主键字段)**在执行的时候，如果表里存在二级索引，优化器就会选择二级索引进行扫描。

所以，如果要执行 count(1)、 count(*)、 count(主键字段) 时，尽量在数据表上建立二级索引，这样优化器会自动采用 key_len 最小的二级索引进行扫描，相比于扫描主键索引效率会高一些。

再来，就是不要使用 count(字段) 来统计记录个数，因为它的效率是最差的，会采用全表扫描的方式来统计。如果你非要统计表中该字段不为 NULL 的记录个数，建议给这个字段建立一个二级索引。

优化count

如果数据量很大，因为要全表扫描，所以也要花费不短的时间

1.使用explain 出现的rows 字段值就是 explain 命令对表 t_order 记录的估算值。

2.额外表保存记录值

 

索引失效的情况

• 当我们使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 这两种方式都会造成索引失效；
• 当我们在查询条件中对索引列使用函数，就会导致索引失效。
• 当我们在查询条件中对索引列进行表达式计算，也是无法走索引的。
• MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
• 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。
• 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。