My-Project

Appearance

B树 & B+树 & innodb当中的B树 ​

区别 ​

B树是一种多路非递归树，B+树是B树的变体。B+树相对于B树有如下特点：

  • 叶子结点当中存在双向指针
  • 每个叶子结点的数据在非叶子节点当中都有冗余
  • 排序（有序）
  • 一个节点当中会存多个数据

innoDb B树 ​

在以下sql当中，创建了一个表t，并且设置了主键自增，

sql
CREATE TABLE `t` (
  `a` int(4) NOT NULL AUTO_INCREMENT,
  `b` int(4) DEFAULT NULL,
  `c` int(4) DEFAULT NULL,
  `d` int(4) DEFAULT NULL,
  `e` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

在innodb当中，B树在插入的时候，会通过主键进行默认排序。这个时候就相当于一个列表。并且设置了主键自增，后续插入的时候会往后插入，性能更快

但是我们都知道，链表的插入数据快，但是查询的时候要遍历链表，所以B树在插入的时候，会通过主键进行排序，这样在查询的时候，就可以通过二分查找的方式，找到数据，所以查询的时候，性能会更好。

page 页 ​

在mysql当中一页（page）默认就会存储16k的数据。可以将这个Page表示为以下Java的Page类。其中Row表示一行数据。当这个Page对象的大小超过了16KB。会重新创建一个Page对象，然后将数据进行存储

java
class Page{
    // 当然这个page当中还包括一些其他的属性等等
    List<Row> list;
}

两层B+树能存多少数据？ ​

在B+树当中，树的层次越多，也就代表着存储的数据越多。遍历查询的效率就越慢。

sql
-- 当B+树当中一个主键int占用10个字节，那么16KB就可以存1638个page页对象
select 16 * 1024 / 10; -- 1638.4
-- 若一条数据占用了1kb，那么1638个page页对象也就是两层的B+树当中可以存26208条数据
select 1638 * 16 / 1;
-- 同理，三层的B+树当中可以存524288条数据
select 1638 * 16 * 16 / 1;

主键索引查询 & 全表扫描 ​

在innodb当中，会使用主键生成一个B+树，当查询的where条件当中，如果使用的是主键索引，那么就会使用B+树进行查询，如果使用的是非主键索引，那么就会使用全表扫描。

SQL
select * from t where a = 1; -- 使用主键索引查询
select * from t where b = 2; -- 使用全表扫描

手写笔记一 ​

联合索引 bcd ​

在这里创建一个联合索引，这里会根据b,c,d创建一个B+树，里面的节点会存储b,c,d三个字段和对应的主键

后续在查询的时候，会根据b,c,d进行查询，然后通过主键进行查询（回表）

sql
create index idx_bcd on t(b,c,d);

在以下sql当中，那些条件会走索引查询，哪些条件不会走索引查询？

sql
select * from t where b = 1 and c = 2 and d = 3; -- 会走bcd索引查询
select * from t where c = 2 and d = 3; -- 不会走bcd索引查询，因为不符合最左前缀原则
-- 使用explain语句，可以查看执行计划
explain select * from t where b = 1 and c = 2;

最左前缀原则： 取索引中最左字段b，在where条件后有无来判断

范围查询导致索引失效 ​

还是在这个表，当表的数据在1-100条数据的时候，执行以下sql

sql
select * from t where b > 1; -- 不会走索引查询
select * from t where b > 99; -- 会走索引查询

在MySQL当中，当索引字段的值在范围查询当中，会做索引查询的回表次数 & 全表扫描的效率，从而决定是否走索引查询。

手写笔记二 ​

覆盖索引 ​

当查询的字段在索引当中，就可以称为覆盖索引，不需要做回表操作，会利用索引

sql
select b from t where b > 1; -- 覆盖索引查询

索引扫描底层原理 ​

这里没有where条件，但还是会走索引查询，这是因为在bcd索引当中，b,c,d三个字段都在索引当中，所以会走索引查询，而不会走全表扫描

并且在bcd索引的B+树当中，存的数据会比主键的B+树的数据少，也就相当于bcd索引的树当中的一页存的数据更多，在查询的时候遍历的页Page越少，效率越高

sql
select b from t; -- 会走bcd索引查询

order by 导致索引失效 ​

sql
select * from t order by b,c,d;
-- 全表扫描 遍历所有的数据 在内存当中进行排序
-- bcd索引 在B+树当中是排序之后的，取出来的数据不需要重新排序了，但是由于是select * 所以需要进行回表操作

select b from t order by b,c,d;
-- 如果是select b，就会走索引查询，因为b在索引当中，而且是覆盖索引，不需要回表操作

MySQL当中的数据类型转换导致索引失效 ​

在mysql当中，在查询的时候会进行默认转换，

sql
SELECT * FROM t WHERE a = 'asd' + 1 ; -- 这里的 'asd' 字符串会转换成数字 1  这个也就相当于 a = 1
SELECT * FROM t WHERE a = 1 + '2' ; -- 但是当'12' 字符串可以转成数字的时候就是数字相加，相当于 a = 3

所以在判断索引的时候，一定要注意数据类型转换，不然就会导致索引失效。

By Modify.

Copyright © 2023-present Evan You