B Tree、B+ Tree和B*Tree

点我复习

MySQL索引

索引是在存储引擎层实现的，而不是在服务器层实现的，不同的存储引擎具有不同的索引类型和实现。

哈希索引

哈希索引可以用O(1)时间进行查找，但是失去了有序性：

  • 无法用于排序与分组
  • 只支持等值查询，无法用于范围查找和不等关系查找

InnoDB存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

B+-Tree索引

这是大多数MySQL存储引擎的默认索引实现。因为B+Tree的有序性，可以实现精确查找，范围查找，排序和分组。可以指定多个列作为索引列，多个索引列共同组成键。适用于全键值、键值范围和键前缀查找，其中键前缀查找只适用于最左前缀查找。如果不是按照索引列的顺序进行查找，则无法使用索引。

InnoDB 的 B+Tree 索引分为主索引和辅助索引。

  • 主索引，在primary key上建立的索引，在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶子节点data域保存了完整的数据记录，因此InnoDB表数据文件本身就是主索引，又称聚簇索引。所以InnoDB要求表必须有主键。
  • 辅助索引，在MyISAM中，辅助索引的结构和主索引一致，叶子节点存储的都是数据记录的地址，InnoDB中，辅助索引的叶子节点存储的都是主索引的主键值。通过辅助索引查找数据，先要在查找到主键，然后根据主索引查找到对应数据

全文索引

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。查找条件使用 MATCH AGAINST，而不是普通的 WHERE。全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。

普通查询select * from article where content like '%查询字符串%'

全文索引查询select * from article where MATCH(content) against ('查询字符串')

空间索引

MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。适合数据库存在多列，会经常根据不同场景来进

索引创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 CREATE  TABLE  table_name(
   属性名  数据类型 [约束条件],
   ……
   属性名  数据类型
   [UNIQUE  |  FULLTEXT   |   SPATIAL  ]   INDEX  |  KEY
   [  别名 ]  (  属性名1   [(  长度  )]   [  ASC  |  DESC  )
 );

属性值的含义如下:
a.  UNIQUE: 可选参数，表示索引为唯一索引。
b.  FULLTEXT:  可选参数，表示索引为全文索引。
c.  SPATIAL:  可选参数，表示索引为空间索引。
d.  INDEX  和 KEY 参数用于指定字段为索引的，用户在选择时，只需要选择其中的一种即可。
e.  "别名" : 为可选参数，其作用是给创建的索引取新名称。
d.   属性名1:  指索引对应的字段名称，该字段必须被预先定义。
f.   长度:  可选参数，其指索引的长度，必须是字符串类型才可以使用。
g.  ASC/DESC: 可选参数，ASC 表示升序排列，DESC 表示降序排列。

索引的使用

单列索引

本质是利用二分查找的思想，将全表扫描的O(n)复杂度简化到对数复杂度

  • 索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引

    错误示例：

    1
    2
    SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;
    SELECT actor_id FROM sakila.actor WHERE DateFormat(birthday) = '2019-01-01';

  • 模糊查询时，第一个字符不能是通配符，否则无法使用索引，本质原因字符串排序按照首字母到尾字母自然顺序排序

  • 负向查询条件：NOT、!=、<>、!<、!>、NOT IN、NOT LIKE等，会导致全表扫描

  • 如果MySQL估计使用全表扫描比使用索引快，则不适用索引

多列索引

在需要使用多个列作为条件进行查询时，使用多列索引比使用单列索引性能更好，本质就是复合排序。让选择性(不重复的索引值和记录总数的壁纸)最强的索引列放在前面，可以快速缩小查询集规模。

1
2
SELECT film_id, actor_ id FROM sakila.film_actor WHERE actor_id = 1 AND film_id = 1;
# 设置actor_id,file_id为联合索引

  • 最左匹配原则

    ABC联合索引，进行A，AB，ABC查询时可以用到联合索引，其他排列组合方式均用不到索引

前缀索引

对于 BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引，只索引开始的部分字符。对于前缀长度的选取需要根据索引选择性来确定。

索引的优点

  • 大大减少了服务器需要扫描的数据行数。
  • 帮助服务器避免进行排序和分组，以及避免创建临时表（B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY 操作。临时表主要是在排序和分组过程中创建，因为不需要排序和分组，也就不需要创建临时表）。
  • 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）。

索引的使用条件

  • 对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效；
  • 对于中到大型的表，索引就非常有效；
  • 但是对于特大型的表，建立和维护索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。