二分查找
二叉树
二叉平衡树
B-TREE ：二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小
缺点：业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及 CPU 高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。
B+TREE：非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据所在的地址
聚簇索引和非聚簇索引
如果叶子节点存储的是实际数据的就是聚簇索引，一个表只能有一个聚簇索引；如果叶子节点存储的不是实际数据，而是主键值则就是二级索引，一个表中可以有多个二级索引。
在使用二级索引进行查找数据时，如果查询的数据能在二级索引找到，那么就是「索引覆盖」操作，如果查询的数据不在二级索引里，就需要先在二级索引找到主键值，需要去聚簇索引中获得数据行，这个过程就叫作「回表」
磁盘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 的记录个数，建议给这个字段建立一个二级索引。
如果数据量很大，因为要全表扫描，所以也要花费不短的时间
1.使用explain 出现的rows 字段值就是 explain 命令对表 t_order 记录的估算值。
2.额外表保存记录值
索引失效的情况
- 当我们使用左或者左右模糊匹配的时候，也就是
like %xx或者like %xx%这两种方式都会造成索引失效； - 当我们在查询条件中对索引列使用函数，就会导致索引失效。
- 当我们在查询条件中对索引列进行表达式计算，也是无法走索引的。
- MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
- 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。
- 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。
Original: https://www.cnblogs.com/zz01/p/16488082.html
Author: 山野村夫01
Title: 索引的树结构
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/622571/
转载文章受原作者版权保护。转载请注明原作者出处！