文章目录

• • 一、索引数据结构
  • • 查找二叉树
    • 平衡二叉树
    • 红黑树
    • B树
    • B+树
  • 二、mysql数据存储方式
  • • 表空间数据结构
    • InnoDB数据页结构
    • InnoDB 行记录格式
    • 行溢出
  • 三、mysql索引
  • • 聚集索引
    • 非聚集索引
    • 哈希索引
    • 全文索引
    • 索引的思考
    • 正确的使用索引
    • 表索引实例
    • 索引与锁
  • 四、维护索引和表

一、索引数据结构

​ 索引：存储引擎用来快速查找数据的一种数据结构。索引是查询数据进行性能优化最有效的手段。不同的存储引擎对于索引的实现不尽相同。以Mysql中的常见的存储引擎Innodb和Myisam为例，两种索引的实现底层都是B+树。

​ 在学习B+树之前我们先了解一下有关二叉树相关结构。

​ 各种数据结构在增删改查的时间复杂度

给大家推荐一款旧金山大学开发的 数据结构动态演示图 可以针对大部分数据结构进行 curd的动态演示，本篇索引数据结构图示均在此生成。

查找二叉树

查找二叉树: 任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。 如下图所示：

​ 二叉搜索树-正常版本

缺点：极端情况树会出现左倾或者右倾。查找的时间复杂度就和链表相同O(n) 如下图所示：

​ **左倾二叉搜索树 **

​ **右倾二叉搜索树 **

平衡二叉树

平衡二叉树: 平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过1。

• 优点：查找效率更稳定，总体的查找速度也更快

• 缺点：每一个节点只存储一个数据信息，从磁盘中获取只能获取一个数据，性能开销比较大，同时海量数据会导致树很高。

红黑树

红黑树（Red Black Tree）是一种自平衡的二叉查找树，它与平衡二叉树相同的地方在于都是为了维护查找树的平衡而构建的数据结构

性质：

• 节点为红色或者黑色

• 根节点和叶子节点为黑色

• 红(黑)色节点的子节点都是黑(红)色

• 从红黑树的任一节点到其每个叶子节点的所有路径都包含相同数目的黑（红）色节点
  
  红黑树和平衡二叉树都是为了解决查找二叉树的平衡问题而衍生出来不同的解决方案。

红黑树和平衡二叉树区别

1. 维持平衡的方式不同

   平衡二叉树：通过左右子树的高度差绝对值不超过1来维持二叉树的平衡。

   红黑树：通过红黑树节点联系来维持二叉树的平衡。

2. 旋转次数不同

   平衡二叉树：插入或者删除节点时为了保证左右子树的高度差会进行旋转。数据不同旋转的复杂度，频繁的插入、修改中造成的效率问题。

   红黑树：红黑树在执行插入修改的操作时会发生旋转与变色（红变黑，或者黑变红）以确保没有一条路径会比其它路径长出两倍。

   在插入或者删除节点时，红黑树旋转的次数比平衡二叉树少，因此在插入与删除操作比较频繁的情况下，选用红黑树。

B树

​ B树和B+树的出现都是为了减少磁盘IO的操作。

​ 上述的平衡二叉树虽然查询效率获取了提升，因为树的每一个节点只存储一条记录，要知道每次获取数据都需要从磁盘获取数据，如果每次只获取一次数据，频繁的磁盘读取。同时面对海量数据会导致树很高,从而也影响查询效率，所以B树(B-tree)将多个数据存放到一个节点，每次读取数据一次磁盘操作可以获取多条数据。

​ B树(平衡多路查找树)：

• 每个节点存储多个元素。 (减少磁盘IO)
• 摒弃二叉树结构，采用多叉树。 (树会变的矮胖)
• 每个节点都是一页（mysql数据结构 一页等于16KB）

B+树

​ B+ 树是对 B 树的进一步优化。

• B 树节点中不仅存储键值，也会存储数据，B+ 树非叶子节点上是不存储数据的，仅存储键值，如果不存储数据，那么就会存储更多的键值。
• B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单

B+树索引适合全键值、范围查找、键前缀查找、最左前缀查找

二、mysql数据存储方式

表空间数据结构

-- 创建表
CREATE TABLE `user` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主鍵',
  `cust_no` varchar(20) DEFAULT NULL COMMENT '客户号',
  `first_name` varchar(50) DEFAULT NULL COMMENT '姓',
  `last_name` varchar(50) DEFAULT NULL COMMENT '名',
  `age` int(5) DEFAULT NULL COMMENT '年龄',
  `sex` int(2) DEFAULT NULL COMMENT '性别',
  `desc` varchar(500) DEFAULT NULL COMMENT '描述',
  `birthday` timestamp NULL DEFAULT NULL COMMENT '出生日期',
  PRIMARY KEY (`id`), #主键索引
  UNIQUE KEY `IDX_CUST_NO` (`cust_no`), #唯一索引
  KEY `IDX_JOINT_NAME` (`sex`,`last_name`), #联合索引
  KEY `IDX_ALIAS` (`alias`), #普通索引
  FULLTEXT KEY `IDX_DESC` (`desc`) #全文索引
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

上述建表语句被执行后，会生成一个user.idb表空间文件。其存储结构如下：

表空间被划分为多个连续的数据区，256个连续的数据区称为一个数据区组(1256MB = 256MB)，一个数据区(6416Kb =1MB)又由64个连续的数据页组成，数据页（16KB）包含数据行

InnoDB数据页结构

InnoDB 行记录格式

InnoDB一共有四种行格式compact、redundant、dynamic、compressed，这里主要展示compact行格式,其他的行格式大同小异。

• 变长字段长度列表：字段类型为 varchar 的字段长度，按照列顺序逆序排列
• null值列表：记录字段是否为null，0：非null，1：null，占用1个字节
• 数据头： 40位，固定占用5个字节
• 隐藏列：
  • DB_ROW_ID：如果 Innodb 没有指定主键，会生成一个rowid列，6字节
  • DB_TRX_ID：事务ID，6字节
  • DB_ROLL_PTR：回滚指针，7字节
    

行溢出

如果一个表中的字段数据总量大于16KB,则会出现行溢出的情况，会将多余的数据（存放不了的数据）拆分到不同的数据页存储，只存放指针指向该页，读取该行记录的时候也需要加载多个数据页到缓冲池中。不同数据格式处理行溢出也不尽相同。

三、mysql索引

聚集索引

​ 在InnoDB中，每张表都有一个主键，如果再创建表时没有显示的定义主键，则InnoDB会按如下方式选择或创建主键：

• 否有非空的唯一索引，如果有，则该列即为主键,多个非空唯一索引选择第一个。
• 如果不符合上述条件，InnoDB自动创建一个6字节大小的指针ROW_ID。

通过在上述user表中，id是自增主键，针对id生成一个聚集索引，聚集索引即属于索引段又是数据段，因为其叶子节点存储索引之外还会存储该行记录。如下图所示：

mysql中B+树的高度一般是3到4层

聚集索引的叶子节点哪处理包含数据外，还包含事务id,回滚指针。

UUID和顺序值做主键的区别

• 顺序主键中因为是顺序的记录都是在页中顺序存储，达到最大的填充因子(15/16 留出的部分用于后续修改)，下一条记录写到新页。
• uuid写入乱序会导致每次插入数据 会改变聚集索引的树状态从而导致页分裂

非聚集索引

上述的聚集索引一个表中只有一个，但是非聚集索引可以有多个，除了主键索引的其他索引类型生成的索引结构都是非聚集索引，其和聚集索引最大的区别是其叶子节点除了存储索引之外并不存储全部的数据而是存储 主键指针。如下所示为非聚集索引结构图：

所以通过非聚集索引查询行完整数据需要查询两遍索引树。比如上述根据姓名建立的普通索引 查询“薛之谦” 需要先遍历姓名建立的非聚集索引树查找到主键索引对应的索引值,然后在遍历逐渐索引树获取到完整的数据。

其他索引建立的索引树结构和该非聚集索引类似，此处不在叙述。

哈希索引

哈希索引基于哈希表实现，当为某个列建立一个hash索引后，对于插入的每一行数据会根据该列计算出一个hash值，则hash表中存储该hash值和对应数据的指针。

Mysql的memory引擎是唯一显式支持hash索引（多个hash值相同会以链表的形式存储）。

同时InnoDB引擎有一个特殊功能为"自适应hash索引"，当InnoDB注意到某些非聚集索引(二级索引、辅助索引)值被使用的非常频繁，则会在内存中基于B树索引在建立一个hash索引以方便快速查找。（这属于引擎内部自发行为，用户无法控制）

• 优点

  hash查找时间复杂度为O(1) ，查找速度快，非常适合精确查找

• 缺点

  hash索引不是按照索引值顺序存储的，无法用于排序查找。

  对于联合索引不支持最左匹配原则（联合索引 是使用索引列的全部内容来计算hash值的）。

  hash不支持范围查找

  hash会产生冲突，如果冲突多，则查找速度也会变慢。

全文索引

​ 全文索引是一种特殊类型的索引，查找的是文本中的关键字、类似于检索引擎做的事情而非简单的where条件匹配。

索引的思考

索引的好处显而易见，但是使用索引我们需要衡量其在查找效率和维护索引之间的成本,对于数据量非常小(大概一万条以下)的表有无索引并不会对性能有啥影响，中到大型表(十万到几百万数据了)使用索引效果会很好，特大型的表(数据量达到千万量级以上)使用和建立索引的代价比较高所以建立分库分表。所以索引并不是万能的解决方案。

所以需要特大型表需要使用到：分区技术、块级别元数据技术、分库分表来处理性能瓶颈。此为后话，以后单独开篇学习汇总。

正确的使用索引

三星系统

评估一个查询是否适合某个查询的“三星系统”（three-start system）：
一星：在一系必要的列上建立索引，不必为在where条件里面的列都建立索引。
二星：将选择性最高的列放到索引的最前列。
三星：覆盖索引：索引中的列包含了查询中需要的全部列。索引包含查询所需要的数据列，不再进行全表查表。

本片学习如何使用索引场景：1、特殊案例的优化方法、2、评估不同索引的性能

索引列不能为表达式或者函数

# 如果age列为索引 则查找条件 age+1 会被看成新的列从而导致索引失效
select name from user where age + 1 =${age};
# 所有查找列不能使用表达式 (合法的方式)
select name from user where age  = ${age}-1;

# 如果age列为索引 则查找条件为函数会被看成新的列从而导致索引失效
select name from user where now（）- TO_DAYS(birthday) =${age};

前缀索引

对于长的字符串建立索引，索引会变的大且慢，所以需要考虑针对字符串的开始的部分字符建立“前缀索引”，这样需要考虑索引选择性：部分字符创建的不重复的索引值和记录总数的比值 (distinct cloum)/total 比值越接近于1则索引选择性越高查询效果越好。

如何计算合适的索引选择性

# 该条sql可以计算某个字符串全部字符建立索引的最高索引选择性
select count(DISTINCT cloumName)/count(*) from tableName；

# 尝试获取最接近上述选择性的 前缀长度
select count(discintct left(cloumName,6))/count(*) as sel3,
count(discintct left(cloumName,7))/count(*) as sel4,
count(discintct left(cloumName,8))/count(*) as sel5
....
from tableName   
   
# 创建前缀索引
ALTER table tanleName ADD key(clumne(7));

有点鸡肋,数据随时在变,前缀索引可能需要调整

多行索引

1. 索引合并问题

#5.0MySql之前 or查询无法使用多个单列索引 
#5.0以后有新特性为索引合并 才可以使用多个单列索引

#该sql在5.0之前 无法使用索引，5.0之后才可以使用
select * from tableName where indexCloumn1 = 1 or indexCloumn2 =2

​ 如果对于需要频繁对多个单列索引进行合并操作（and、or）可以考虑使用多行索引，因为索引联合操作需要消耗cpu和内存资源，而且优化器不会考虑其“查询成本”，导致查询成本被低估从而导致执行计划还不如走全表扫描。

2. 索引列顺序

   正确的多行索引顺序需要满足 查询,排序、

• 不考虑分组和排序，将索引选择性高的放在联合索引前面。

覆盖索引

如果索引的叶子及诶单已经包含要查询的数据则该索引为“覆盖索引”。会避免会表。

排序索引

​ 所谓排序索引是使用索引本身的有序性从而避免查找完数据再次进行排序的性能损耗。

​ 单列索引也属于多行索引，

1. 只有当索引的列顺序与order by 子句的顺序完全一致，并且所有列的排序方向（倒叙或者正序）都一样时，mysql才能够使用索引来对结果进行排序。
2. 如果查询需要关联多张表的时候，则只有当order by子句引用的字段全部为第一张表时，才能使用索引排序，order by子句和查找型查询的限制是一样的：需要满足索引的最左前缀的要求。

表索引实例

多中过滤条件

参考上述的user表

1. 哪些查询条件出现频繁（频繁的查询条件需要考虑建立索引）cust_no建立索引。

2. 查询条件选择性更高的建立索引，cust_name选择性比sex高。（特例比如sex 选择性低 但是查询频繁 可以做联合索引的第一列 为了最左匹配 可以使用 in(‘f’,‘m’)）。

3. 考虑排序的话，尽量做到索引排序 order by age 则age 尽量作为索引从而使用索引排序。

避免多个范围查找

​ 如果一个查询条件中同时使用两个字段(两个字段均有索引)进行范围查找，则无法同时使用两个字段索引

比如 查找age在18-20之间，score学分在80-90的用户，两列索引不会同时使用。

排序优化

对于查找选择性低的用户并进行排序，比如sex,则可以将其和一个选择性高的列组合成联合索引，通过如下语句优化

# 建立(sex,score)联合索引
# 注意limit很重要 太大也会导致后面的查询变慢。
select * from user where sex = "M" order by score limit 10 

索引与锁

合适的索引可以减少行锁定，但是只有存储引擎层能过滤掉不需要的行才能有效，如果只有查询到了数据再应用where语句则还是会锁定不需要的行，比如如下sql

# 只有第一个查询条件 id <5 被使用到存储引擎，第二个查询条件 id!=1 只有在存储引擎返回1-4数据 
#再应用第二个查询条件过滤掉id=1的数据，则多锁了id=1的行记录
# for update 为其隐式加添写类型的拍它锁。
select * from user where id <5 and id !=1 for update

四、维护索引和表

1. 查询数据库的数据行数、表空间、索引空间

#可以查询数据库的数据行数、表空间、索引空将 [数据库名] 替换成你自己的数据库名即可。
SELECT TABLE_SCHEMA AS '库名',
CONCAT(ROUND(TABLE_ROWS/10000, 2), ' 万行') AS '行数',
CONCAT(ROUND(SUM(DATA_LENGTH)/(1024*1024*1024), 2), ' GB') AS '表空间',
CONCAT(ROUND(SUM(INDEX_LENGTH)/(1024*1024*1024), 2), ' GB') AS '索引空间',
CONCAT(ROUND(SUM(DATA_LENGTH+INDEX_LENGTH)/(1024*1024*1024),2),' GB') AS'总空间'
FROM information_schema.TABLES WHERE TABLE_SCHEMA = [数据库名];

2.修复表

因为硬件、系统崩溃导致表出现问题，所以需要修复表

#常用命令 检查表和索引的问题
CHECK TABLE [tableName]

#修复表
REPAIR TABLE [tableName]
# 不做任何实际操作的alter语句也可修复表
ALTER  TABLE [tableName] ENGINE=INNODB

3. 索引相关

#更新索引统计信息,便于优化器查询的时候计算成本
ANALYZT TABLE [tableName]

#查看索引技术信息
SHOW INDEX FROM [tableName]
#INNODB引擎通过抽样的方式来计算统计信息

减少索引和数据的碎片

​ 在InnoDB中，删除一些行，这些行只是被标记为“已删除”，而不是真的从索引中物理删除了，因而空间也没有真的被释放回收。InnoDB的Purge线程会异步的来清理这些没用的索引键和行。但是依然没有把这些释放出来的空间还给操作系统重新使用，因而会导致页面中存在很多空洞。如果表结构中包含动态长度字段，那么这些空洞甚至可能不能被InnoDB重新用来存新的行，因为空间空间长度不足。所以最终数据会有碎片。

行碎片： 同一行数据被存储到多个页中。

行间碎片：逻辑顺序的页在实际的磁盘存储中不是顺序的。

剩余空间碎片：数据页中有大量的空余空间。

#消除碎片
OPTIMIZE TABLE [tableName]
#重新导入到处数据


#不做任何实际操作的alter语句也可消除碎片
ALTER  TABLE [tableName] ENGINE=INNODB