二分查找
二叉树
二叉平衡树
B-TREE ：二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小
缺点：业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及 CPU 高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。
B+TREE：非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据所在的地址
聚簇索引和非聚簇索引
如果叶节点存储的实际数据是聚集索引，则一个表只能有一个聚集索引；如果叶节点存储的不是实际数据，但主键值是辅助索引，并且一个表中可以有多个辅助索引。
[En]
If the leaf node stores the actual data is a clustered index, a table can only have one clustered index; if the leaf node stores not the actual data, but the primary key value is the secondary index, and there can be multiple secondary indexes in a table.
当使用二级索引查找数据时，如果在二级索引中可以找到查询到的数据，那么这就是“索引覆盖”操作。如果查询的数据不在二级索引中，则需要先在二级索引中找到主键值。如果您需要获取聚集索引中的数据行，则此过程称为“返回表”。
[En]
When using the secondary index to find data, if the queried data can be found in the secondary index, then it is the “index overwrite” operation. If the queried data is not in the secondary index, you need to find the primary key value in the secondary index first. If you need to get the data rows in the clustered index, this process is called “returning to the table”.
磁盘IO
磁盘处理太慢太慢了
- 尽量减少 I/O 次数，比如可以使用缓存；
- 每次 I/O 尽量获取更多的数据；
- 每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数
总结：
- 数据存储在磁盘（ SSD 跟 CPU 性能也不在一个量级），而磁盘处理数据很慢；
- 提高磁盘性能主要通过减少 I/O 次数，以及单次 I/O 有效数据量；
- 索引通过多阶（一个节点保存多个数据，指向多个子节点）使树的结构更矮胖，从而减少 I/O 次数；
- 索引通过 B+ 树，把业务数据与索引数据分离，来提高单次 I/O 有效数据量，从而减少 I/O 次数；
- 该索引通过对树数据进行排序和“二分查找”(多序树可假定为多部分搜索)，大大缩小了查询范围。
[En]
the index greatly reduces the scope of the query through the ordering of tree data and “binary search” (multi-order trees can be assumed to be multi-part search).*
索引针对单个字段或部分字段，数据量本身远小于一条记录，因此扫描查询索引比扫描数据库表本身要快得多。
[En]
the index is aimed at a single field or part of the field, and the amount of data itself is much less than that of a record, so that querying the index by scanning is much faster than scanning the database table itself.*
-
持久性是通过 redo log （重做日志）来保证的；是物理日志，记录做了什么修改
- 原子性是通过 undo log（回滚日志） 来保证的；
- 一致性是binlog保证的 ，逻辑日志（有三种格式）statement，row包含操作的具体数据，mixed
- 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
死锁问题
处理订单业务时，需要用到select…for update用来避免并发导致的幻读问题，但是这样的话就容易出现死锁
应对的办法是摧毁形成僵局的条件：打破循环，等待条件。
[En]
The way to deal with it is to destroy the conditions that form a deadlock: break the cycle and wait for conditions.
-
设置事务等待锁的超时时间。当一个事务的等待时间超过该值后，就对这个事务进行回滚，于是锁就释放了，另一个事务就可以继续执行了。在 InnoDB 中，参数
innodb_lock_wait_timeout是用来设置超时时间的，默认值时 50 秒。 -
开启主动死锁检测。主动死锁检测在发现死锁后，主动回滚死锁链条中的某一个事务，让其他事务得以继续执行。将参数
innodb_deadlock_detect设置为 on，表示开启这个逻辑，默认就开启。
关于count
- count(1)、 count()、 count(主键字段)**在执行的时候，如果表里存在二级索引，优化器就会选择二级索引进行扫描。
所以，如果要执行 count(1)、 count(*)、 count(主键字段) 时，尽量在数据表上建立二级索引，这样优化器会自动采用 key_len 最小的二级索引进行扫描，相比于扫描主键索引效率会高一些。
再来，就是不要使用 count(字段) 来统计记录个数，因为它的效率是最差的，会采用全表扫描的方式来统计。如果你非要统计表中该字段不为 NULL 的记录个数，建议给这个字段建立一个二级索引。
如果数据量很大，则需要很长时间，因为需要进行全表扫描。
[En]
If the amount of data is large, it will take a long time because the full table scan is required.
1.使用explain 出现的rows 字段值就是 explain 命令对表 t_order 记录的估算值。
2.额外表保存记录值
索引失效的情况
- 当我们使用左或者左右模糊匹配的时候，也就是
like %xx或者like %xx%这两种方式都会造成索引失效； - 在查询条件中对索引列使用函数时，会导致索引失败。
[En]
when we use functions on index columns in query conditions, it will cause the index to fail.*
- 当我们计算查询条件中索引列的表达式时，也不可能遍历索引。
[En]
when we evaluate the expression of the index column in the query condition, it is also impossible to walk the index.*
- MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
- 如果联合索引能够正确使用，则需要遵循最左边的匹配原则，即按照最左边的优先级匹配索引，否则会导致索引失败。
[En]
if the federated index can be used correctly, it needs to follow the leftmost matching principle, that is, to match the index according to the leftmost priority, otherwise it will cause the index to fail.*
- 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。
Original: https://www.cnblogs.com/zz01/p/16488082.html
Author: 山野村夫01
Title: 索引的树结构
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/505204/
转载文章受原作者版权保护。转载请注明原作者出处！