索引的树结构

mysql 文章 2022-07-20 10:07 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 后的条件列不是索引列,那么索引会失效。
-EOF-