目录与学习目标

  1. 1：索引总览
  2. 2：二叉树（Binary Search Tree）
  3. 3：红黑树（Red/Black Tree）
  4. 4：B-Tree
  5. 5：B+Tree（B-Tree的变种）
  6. 6：Hash索引
  7. 7：MyISAM索引引擎 与 InnoDB索引引擎  
  8.     1：数据库引擎索引
  9.     2：MyISAM索引文件和数据文件是分离的
  10.     3：InnoDB索引实现
  11. 8：InnoDB索引引擎总结
  12. 9：联合索引（排好序概念的深度理解）

1：索引总览

  1. 索引引擎结构（重要 重要 重要 ）（先有印象）：
  2.     InnoDB索引引擎   索引可以存储  data数据本身
  3.     MyISAM索引引擎  索引可以存储  data的地址
  5. 什么是索引：
  6.     索引      是帮助MySQL高效获取数据   的排好序的数据结构
  8.     索引是排好序的数据结构（哪怕该索引插入进去的时候是无序的，它也会进行索引维护来排序）
  10.     数据的查询效率 看的是进行IO的次数
  11.     树越高 需要进行 IO次数 也就越多
  13. 索引数据结构
  14.     二叉树（无法解决平衡 无法解决树高）
  15.     红黑树（解决局部平衡 无法解决树高）
  16.     B-Tree （无法极致的解决树高 无法极致的解决范围查找）
  17.     B+Tree （MySQL索引使用数据结构  支持等值查找 支持范围查找）    
  18.     Hash表（仅限于 等值查找  不支持范围查找）
  1. 注意：
  2.     索引引擎    的结构：仅代表存放数据与索引的位置（文件位置）
  3.     索引  的数据结构：存放数据与索引的的数据结构

2：二叉树（Binary Search Tree）

  1.  数据无序：
  2. select * from table where Col2=89 
  3. 1：如果没有索引 全表扫描磁盘 需要查找6次
  4. 2：如果有二叉树索引  需要查找2次
  6. 数据递增：
  7. select * from table  where Col1 = 6
  8. 1：如果没有索引 全表扫描磁盘 需要查找6次
  9. 2：如果有二叉树索引 也是需要查找6次    
  10. 这也就是为什么MySQL当数据是递增（自增的主键）的时候，
  11. 为什么不选择二叉树的原因。

image.png
image.png

3：红黑树（Red/Black Tree）

  1. 1：根节点是黑色的
  2. 2：其他节点是红色或黑色
  3. 3：每个红色节点必须有两个黑色的子节点
  4. （从每个叶子到根的所有路径上不能有两个连续的红色节点）
  5. 4：从任一节点到其每个叶子的所有简单路径
  6.     都包含相同数目的黑色节点
  8. 遵循如上规则的二叉树被称为红黑树，但是为什么要定义成如上规则呢？
  9. 事实上，如上所有的规则都只想做一件事，让二叉树尽可能的平衡。

image.png
image.png
image.png

  1. 当数据量大的时候 树会变得特别特别高
  2. 从根节点到对应的叶子节点的查询效率非常慢
  4. 最根本的问题：树的高度

4：B-Tree

  1. 1：节点中的数据索引从左到右递增排列
  2. 2：叶节点具有相同的深度，叶节点的指针为空
  1. 注意：所有索引元素不重复
  3. 特点：非叶子节点可以存储data（真正的数据）

image.png

  1. 设置每一个索引页最多存储4个索引子页（注意索引元素不重复）

image.png

5：B+Tree（B-Tree的变种）

  1. 1：节点中的数据索引从左到右递增排列
  2. 2：叶节点具有相同的深度，叶节点的指针为空
  1. 注意：索引元素会重复
  3. 特点    
  4.     1：非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
  5.     2：叶子节点包含所有索引字段
  6.     3：叶子节点用指针连接，提高区间访问的性能

image.png

  1. 设置每一个索引页最多存储4个索引子页（或数据）（注意索引元素可能重复）

image.png

  1. 如何进行查找：比如查找30
  2. 1：把根节点的索引数据页 加载到内存（慢）  使用折半查找（二分法）（快）
  3. 2：查找到 15的索引数据页
  4. 3：把15的索引数据页 加载到内存（慢）  使用折半查找（二分法）（快）
  5. 4：查找到 20的索引数据页
  6.     以此类推
  7. 5：查找到30这个索引   然后使用这个索引去磁盘里面找数据（慢）
  9. 查找索引所在索引页的位置    相对于    磁盘IO来说      可以忽略不计
  11. Mysql 的每一个索引页有多大：16KB（官方默认值  不建议修改） 
  12. SHOW GLOBAL STATUS LIKE 'INNODB_page_size'
  14. MYSQL索引的最大数据类型为bigint（8个字节）   索引指向地址的指针6个字节
  16. 16KB 的索引页可以存储 16KB 除以14字节 = 1170     
  17. 那么进行两次索引页的IO 
  18. 就可以查找到 1 368 900 个索引
  20. 最后还需要进行一次叶子节点索引页的IO    
  21. 假设一个Data为1KB（后面提及）
  22. 那么一个索引页可以存储 16个DATA
  24. 那么三次IO一共可以查询：21 902 400（2千万条数据）
  26. 注意：
  27.     通过最后叶子节点的链表 实现 范围查询   （对比Hash 索引  后文会提及）

image.png

6：Hash索引

  1. Hash
  2. 对索引的key进行一次hash计算就可以定位出数据存储的位置
  3. 很多时候Hash索引要比B+ 树索引更高效
  4. 理想情况下一次就可以定位到数据存储的位置
  6. hash冲突问题（使用hash碰撞+链表结构 形成hash桶结构）
  8.  但仅能满足 “=”，“IN”，不支持范围查询
  9.  如：name>Alice  导致需要全表扫描

image.png
image.png

7：MyISAM索引引擎 与 InnoDB索引引擎

1：数据库引擎索引

  1. 两者索引都是表级别的索引。（新增表的时候可以选择存储引擎）

image.png

2：MyISAM索引文件和数据文件是分离的

  1. tableName_myisam.frm（表结构）
  2. tableName_myisam.MYI（索引文件）
  3. tableName_myisam.MYD（数据文件）
  5.  索引和数据分开存储的 
  7. B+Tree索引下查询步骤：  
  9. select * from tableName where iCol1 = 30
  10. 1：查询索引文件 tableName_myisam.MYI 查找 iCol1的索引
  11. 2：查询方式按照上述 B+ 树的查找方式
  12. 3：获取 iCol1 = 30 的 数据地址（OxF3）
  13. 3：根据 数据地址（OxF3）  查询数据文件 tableName_myisam.MYD 的对应数据

image.png

3：InnoDB索引实现

  1. tableName_innodb_lock.frm（表结构）
  2. tableName_innodb_lock.ibd（索引文件 和 数据文件）
  4.  索引和数据存储在一起 
  6. 表数据文件本身就是按B+Tree组织的一个索引结构文件
  8. 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
  9. 这里面包含两个问题：1：要有主键 2：整型的主键 3：自增的主键
  10.      1：如果不建立主键，表会默认进行每列遍历，如果哪一列的数据没有重复则取该列为主键 
  11.          都有重复的话，则新增一个隐藏列。
  12.      2：  索引页比对大小，整型是比较数字大小，字符串是比较每一个字母ASCLL码大小
  13.            索引存储的空间，整型比字符串小。
  14.      3：自增的主键，不需要经过索引页的复杂的重排。
  16. 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
  17.     其中又分 聚集索引 和 非聚集索引
  18.     InnoDB的主键（有且唯一） 是聚集索引（主键索引） 叶节点包含了完整的数据记录（一整行数据 ）
  19.     InnoDB的其他索引  是非聚集索引（二级索引）  存储的是主键的位置 （回表操作）

image.png
image.png

8：InnoDB索引引擎总结

  1. MySQL正常情况下都是选择InnoDB引擎：仅代表存放数据与索引的位置（文件位置）
  2. 而InnoDB引擎又选择使用B+Tree索引（存放数据与索引的的数据结构）
  4. InnoDB索引引擎 （索引文件 和 数据文件 放在同 一个文件）
  6. B+Tree：
  7.             主键索引（聚集索引） ：存储该索引 对应的行的所有数据
  9.             非主键索引（非聚集索引）：存储主键索引的数据
  10.             然后需要回表操作（查询主键Data  再查询其他数据信息）

9：联合索引（排好序概念的深度理解）

  1. 最左匹配原则：
  2. 先看最左边的字段  
  4. Key  'idx_name_age_postion'  (`name ` , `age` ,`postion`) USING BTREE
  5. Explain select * from emplayees where name ='Bill' and  age =31 ;
  6. Explain select * from emplayees where  age =30 and position ='dev'  ;  （不走索引）
  7. Explain  select * from emplayees where  position ='manger'  ;   （不走索引）
  9. 因为：索引必须排好序  如果不限制 name  那么在整张表里面age并没有排好序

image.png