mysql系列之索引

发表于 更新于 分类于

mysql系列之索引

索引相关数据结构

Mysql 使用B+树。

索引的作用是为了快速检索/查找。

与查找相关的数据结构：

  • 散列表
  • 二叉查找树以及衍生树结构

散列表

select * from user where id=7;

针对上述查找需求可以满足，hashmap 有数据碰撞问题（链地址/ 红黑树）

select * from user where id>3;

但针对范围查找，不适用

二叉查找树以及衍生树结构

BSF时间复杂度\(O(lgn)\) ，检索效率较高，另外针对范围查询，可以先找到起始点然后查找右子树知道终止点。

二叉树问题： 极端情况-斜树，退化为O(N).

改进： AVL （相对于红黑树，树保持平衡旋转）和 红黑树(非严格平衡)

问题 （可认为树的高度就等于每次查询数据时磁盘 IO 操作的次数。）- 磁盘IO，每个树节点只存储一个数据，树高较高需要多次IO。

磁盘IO一个特点： 一次读取1B和一次读取1KB数据消耗的资源差别不大，因此需要尽量在一个树节点多存储数据。

磁盘读取数据靠的是机械运动，每次读取数据花费的时间包含：寻道时间、旋转延迟时间、传输时间3部分。

B树，B+树

区别

第一，B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。

第二，B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

聚簇索引和非聚簇索引

MYSQL 索引是在存储引擎层实现，

非聚簇索引： 数据和索引分开 （MyISAM）

preview

聚簇索引： 数据和索引一块存储（Innodb）

  • 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

  • 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

例如： userinfo根据主键ID做做key建立索引，执行select * from userinfo where id=15， 查询主索引B+树。只有主键索引会存储具体数据，辅助索引存储主键的引用。 - 节省存储空间，带来的问题要到主键索引B+树查找真正的数据。 user_name 添加索引：

因此，我们在应用中应该尽量使用主键查询。

一般B+树根都会存储再内存（很大概率第二层也在内存）。 比如N为1200，当树高为4可以存储10亿行数据，因此IO次数大幅度减少。

索引维护

写入和删除需要更新索引树，可能需要页分裂。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。

覆盖索引

辅助索引回表问题


mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');
Screen Shot 2020-08-30 at 10.38.18 PM

select * from T where k between 3 and 5

执行过程：在 k 索引树上找到 k=3 的记录，取得 ID = 300；再到 ID 索引树查到 ID=300 对应的 R3；在 k 索引树取下一个值 k=5，取得 ID=500；再回到 ID 索引树查到 ID=500 对应的 R4；在 k 索引树取下一个值 k=6，不满足条件，循环结束。

select ID from T where k between 3 and 5， 因为ID已经在K索引树，可直接提供结果。

盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

联合索引

create table t (
  a int,
  b int,
  primary key (a),
  key idx_a_b (a, b);
) engine = innodb
Screen Shot 2020-09-09 at 2.29.42 PM

select * from t where a =? and b =? 可以使用该联合索引

针对单个a查询，也可以

针对单个b查询，无法使用，因为叶子节点b并不是排好序的

例： buy_log table ： userId， buyDate ， 索引(userid) + 联合索引（userid，buydate）

select * from buy_log where userid=2

Screen Shot 2020-09-09 at 2.57.06 PM

两个索引可以使用，最终优化器选择userid， 因为该索引叶子简单包含单个键值（空间）

select * from buy_log where userid=1 order by buy_date desc limit 3

Screen Shot 2020-09-09 at 2.59.15 PM

因为联合索引在同一个userid情况下buydate已经排好序了，无需额外排序。

如果强制使用userid索引，extra显示using filesort， 即需要额外排序。

Screen Shot 2020-09-09 at 3.24.57 PM 

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

如果有根据身份证号查询市民信息的需求，我们只要在身份证号字段上建立索引就够了

身份证号、姓名）的联合索引:

如果有一个高频请求，要根据市民的身份证号查询他的姓名

最左前缀原则

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。

img

如果查询所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。

如果要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是"where name like ‘张 %’"。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

在建立联合索引的时候，如何安排索引内的字段顺序？

评估标准是，索引的复用能力: 如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

如果既有联合查询，又有基于 a、b 各自的查询呢？查询条件里面只有 b 的语句，是无法使用 (a,b) 这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护 (a,b)、(b) 这两个索引。

比如上面这个市民表的情况，name 字段是比 age 字段大的 ，那我就建议你创建一个（name,age) 的联合索引和一个 (age) 的单字段索引.

索引下推

如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。

mysql> select * from tuser where name like '张%' and age=10 and ismale=1;

前缀索引规则， 语句在搜索索引树的时候，只能用 “张”，找到第一个满足条件的记录 ID3。

MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值。MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

img

Cadinality

B+ 索引针对访问很少一部分数据时 ，并且离散度高才有意义。

eg， 性别， 取值只有M、F， 那么SQL得到的结果是表的50%，B+索引没有必要。

如何确定索引是否有高选择性？ - Cadinality

Cardinality/row_in_table 应尽可能趋近1，如果非常小，可以考虑删除索引。

Cadinality 统计

如果每次索引更新都统计cadinality ，数据库负担重。另外大表统计慢。

采样 - 发生在insert 和 update， 策略：

  1. 表中1/6 数据发生过变化
  2. stat_modified_counter （mysql innodb引擎内部计数器，记录数据变化次数）超过一定阈值

根据叶子节点数，随机取得8个叶子节点，统计每个页不同记录数，计算得出。

索引相关问题

0. 什么场景适合创建索引

  1. 较频繁的作为查询条件的字段应该创建索引；
  2. 唯一性太差的字段不适合单独创建索引，即使该字段频繁作为查询条件；
  3. 更新非常频繁的字段不适合创建索引。

补充2： 离散度高适合索引，否则重复值太多，可能mysql优化器反而会执行全表扫描。

1. 主键的选择问题？

一般要求建表语句都要有自增主键。 结合索引维护相关知识，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂或页合并。

而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

另外业务相关的字段（例如使用身份证），可能会占用树节点更多存储空间。主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

2. 辅助索引回表问题

覆盖索引 章节

3. 左匹配

联合索引 章节

4. 联合索引

联合索引 章节

5. mysql中的N叉B+树，N的调整问题。

可以通过调整数据页的大小间接调整。

6. B+索引使用

OLTP Vs OLAP

在线事务系统一般只是查询数据库中一小部分数据，如根据主键查询用户信息，根据订单号查询订单详细信息，B+索引适用。而统计分析类应用，一般会需要读取大量数据。

6. 索引是否生效如何查看？ 什么时候创建了索引，却没有使用。

索引选择- 查询优化器。

Explain（执行计划） : possiblekeys and key

有时候优化器不使用索引，多发生于范围查找和join

例如： select* from orderdetails where orderid>1000 and ordered < 200000

即使针对orderid 有辅助索引，优化器最终选择了PRIMARY聚集索引，也就是表扫描，因为 用户选取数据是整行，无法使用覆盖索引，如果使用辅助索引需要回表，离散IO操作，也就是如果访问数据量占比大，会选取聚集索引查找。

ForceIndex - 强制使用某个索引

index hint - use index ，只是告诉优化器可以选择哪个索引，并非强制。

Explain 参考 Post not found: mysql系列之执行计划 mysql系列之执行计划

7. 索引越多越好么？

NO

  • 数据量小的表不需要建立索引，建立会增加额外的索引开销
  • 不经常引用的列不要建立索引，因为不常用，即使建立了索引也没有多大意义
  • 经常频繁更新的列不要建立索引，因为肯定会影响插入或更新的效率
  • 数据重复且分布平均的字段，因此他建立索引就没有太大的效果（例如性别字段，只有男女，不适合建立索引）
  • 数据变更需要维护索引，意味着索引越多维护成本越高。
  • 更多的索引也需要更多的存储空间

https://zhuanlan.zhihu.com/p/113917726

https://zhuanlan.zhihu.com/p/73204847

https://zhuanlan.zhihu.com/p/164666142

https://blog.csdn.net/nonage_bread/article/details/108432157

https://blog.csdn.net/qq_38484010/article/details/108184371

https://www.cnblogs.com/eternityz/p/12450466.html