B 树 & B+树

B 树：平衡的多叉查找树，每个节点都包含数据，在任意节点匹配上就返回数据，找不到就返回空指针。

B+树：

  1. 关键字全部存储在叶子节点上，且叶子节点本身根据关键字自小而大顺序连接。
  2. 非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字。
  3. 有 n 棵子树的节点含有 n 个关键字（也有认为是 n-1 个关键字）。
    B+树的查找过程，在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在 B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径。

B+树效率

InnoDB 引擎存储数据的时候以页为单位，一页就是一节点。
每个节点的默认大小是 16KB，一个指针的大小是 6 个字节，主键占用 8 个字节，
一个节点大概有 (161024)/(6+8)=1170 个指针，
当表中一条记录 1KB，单个叶子节点可以存储 16 条数据，
即树高度为 2 时能关联 117016=18720 条数据，当高度为 3，能关联 1170117016=21902400 条数据。

索引

索引是有结构的数据，这些数据结构以某种方式引用（指向）数据，MySQL 的索引使用 B+树的数据结构。

主键索引

InnoDB 叶子节点存行数据；MyISAM 叶子节点是数据的地址指针。

普通索引

InnoDB 叶子节点存主键值；MyISAM 叶子节点是数据的地址指针。普通索引查询到叶子节点主键值，用主键去主键索引查数据，这就是回表查询。

聚集索引

索引顺序和数据的顺序一致，如果索引相邻，对应数据也相邻存放。InnoDB 主键索引就是聚集索引，聚集索引将数据与索引放一起，索引结构的叶子结点保存了行数据，聚集索引有且仅有一个。

  1. 有主键，主键索引就是聚集索引；
  2. 无主键，第一个唯一索引（UNIQUE）为聚集索引；
  3. 无主键、唯一键，InnoDB 会生成一个隐式主键（rowid）作为聚集索引列。

索引查询过程：

  • where id = 14：主键索引树中找到对应叶子节点，获得行数据；
  • where Name = ‘xx’：
    • 辅助索引树中检索 Name，到达其叶子节点获取对应的主键。
    • 再用主键在主键索引树找到对应叶子节点，获得行数据。

非聚集索引

索引逻辑顺序和磁盘中数据的物理顺序不一致。

覆盖索引

查数据时，select 的列刚好是复合索引中涉及的字段，这样能直接返回数据，避免回表，extra 中 Using Index 说明使用了覆盖索引。

最左匹配原则

覆盖索引要求查询字段的顺序与复合索引从左到右的顺序一致才行。

索引条件下推

当存在索引列条件判断时，将条件判断从 MySQL 服务器向下传递给存储引擎，减少 IO 次数，extra 中 Using index condition 说明使用了索引条件下推。

创建索引

普通索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
-- 将 user 表 user_name 列设为索引
create index idx_user_name on user(user_name);

-- 创建email列的索引，索引可以截取length长度，只使用这一列的前几个字符
create index idx_email on user(email(5));

-- 该表方式创建索引
alter table user add index idx_user_name(user_name);

-- 建表时创建索引
create table user (
    id int,
    user_name varchar(20),
    gender varchar(1),
    index idx_user_name (name)
);

-- 删除索引
drop index idx_user_name on user;

唯一索引

1
create unique index idx_user_name on user(user_name);

复合索引

1
create index idx_user_composite_index on user(user_name, email(7));

索引失效

  1. 用 OR 查询；
  2. 违背最左匹配原则；
  3. like 以 % 开头；
  4. 发生类型转换；
  5. where 中索引列有运算；
  6. where 中索引列使用了函数；
  7. 如果 MySQL 觉得全表扫描更快时（数据少）;

OR

  1. 如果条件中有 OR，只要其中一个条件没有索引，其他字段有索引也不会使用。
  2. 如果条件中的字段都有索引，但是 OR 多个字段都需要全表扫描，因此还是会 走全表扫描 或者 全索引扫描；也就是说如果其他字段不符最左前缀原则，但是都是覆盖索引的值，因此走一次全索引扫描

案例

  1. where c1=1 OR c2=2 改成 where c1=1 UNION ALL where c2=2
  2. where id=1 OR id=2 改成 where id in (1,2)