Mysql索引相关

Mysql架构

不同的存储引擎，数据文件和索引文件存放的位置是不同的，因此有了分类：
聚簇索引：数据和文件在一起（InnoDB）
    .frm：存放的是表结构
    .ibd：存放数据文件和索引文件
    注意：mysql的InnoDB存储引擎默认情况下会把所有的数据文件放到表空间中，不会每一个单独的表保存一份数据文件。如果需要将每一个表单独使用文件保存，设置如下属性：set global innodb_file_per_table=on;

非聚簇索引：数据和索引单独一个文件（MyISAM）
    .frm：存放表结构
    .MYI：存放索引数据
    .MYD：存放实际数据

InnoDB与MyISAM存储引擎区别

• 两者主要特点

InnoDB：行级锁、事务安全（ACID）、支持外键。InnoDB存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全存储引擎。
InnoDB是为处理巨大量时拥有最大性能而设计的。它的CPU效率可能是任何其他基于磁盘的关系数据库引擎所不能匹敌的。
InnoDB支持事务处理与外键和行级锁，而MyISAM不支持。

MyISAM：表级锁、不支持事务和全文索引。
适合一些CMS内容管理系统作为后台数据库使用，但是使用大并发、重负荷生产系统上，表锁结构的特性就显得力不从心。

• 两者性能厕所

  随着CPU核数的增加，InnoDB的吞吐量反而越好，而MyISAM，其吞吐量几乎没有什么变化.
  显然，MyISAM的表锁定机制降低了读和写的吞吐量。

• 事务支持与否

  InnoDB是事务安全的;
  事务是一种高级的处理方式，如在一些列增删改中只要哪个出错还可以回滚还原，而MyISAM就不可以了。

MyISAM是一种非事务性的引擎，使得MyISAM引擎的MySQL可以提供高速存储和检索，以及全文搜索能力。
适合数据仓库等查询频繁的应用。

• 两者构成上的区别

  数据和文件在一起（InnoDB）
      .frm：存放的是表结构
      .ibd：存放数据文件和索引文件
  基于磁盘的资源是InnoDB表空间数据文件和它的日志文件，InnoDB 表的大小只受限于操作系统文件的大小，一般为2GB。

每个MyISAM在磁盘上存储成三个文件：
第一个文件的名字以表的名字开始，扩展名指出文件类型，.frm文件存储表定义。
第二个文件是数据文件，其扩展名为.MYD (MYData)。
第三个文件是索引文件，其扩展名是.MYI (MYIndex)

哈希表：哈希冲突

哈希表可以完成索引的存储，每次在添加索引的时候需要计算指定列的hash值，取模运算后计算出下标，将元素插入下标位置即可。
使用场景：
    等值查询
    表中的数据是无序数据（范围查找的时候比较浪费时间，需要挨个进行遍历操作）
在企业中多数的查询时范围查询还是等值查询？
范围查询，所以此时hash表不是特别合适
hash表在使用的时候，需要将全部的数据加载到内存，比较耗费内存的空间也不是很合适。

二叉树及其N多的变种都不能支撑索引，原因是数的深度无法控制或者插入数据的性能比较低。

Mysql索引系统

mysql索引数据结构 B+ Tree

B+ Tree是在B Tree的基础上做的一种优化，变化如下：
1. B+树每个节点可以包含更多的节点，原因有2个：降低树的高；将数据范围变为多个区间，区间越多数据检索越快。
2. 非叶子节点存储key，叶子节点存储key和数据
3. 叶子节点两两指针相互连接（符合磁盘的预读特性），顺序查询性能更高。

注意：在B+树上有两头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点(数据节点)之间是一种链式环结构。
因此可以对B+树进行两种查找运算：对于主键的范围查找和分页查找；另一种是从根节点开始，进行随机查找。

1. InnoDB是通过B+树结构对主键创建索引，然后叶子节点中存储记录。
如果没有主键，那么会选择唯一键；如果没有唯一键那么会生成一个6字节的row_id来作为主键。

2. 如果创建索引的键是其他字段，那么叶子节点存储的是该记录的主键，然后再通过主键索引找到对应的记录，叫做回表。

mysql数据结构选择

• hash表的索引格式
  

  缺点：
  1. 利用hash存储的话需要将所有的数据文件添加到内存，比较耗费内存空间。
  2. 如果所有的查询都是等值查询，那么hash确实很快。但是在企业或者实际工作环境中范围查找的数据更多，而不是等值查询，因此hash就不太适合了。

• 二叉树和红黑树索引格式
  
  

  二叉树：左子树上值小于它的根节点；右子树大于它的根节点；它的左右子树也分别为二叉排序树。
  红黑树：一种平衡二叉树，红黑树的每个节点都有存储位表示节点的颜色，可以是红或者黑。每个节点都是红或者黑；根节点是黑；如果一个节点是红色的，则它的子节点必须是黑色的。
  无论是二叉树还是红黑树，都会因为树的深度过深而造成IO次数变多，影响数据库读取的效率。

• B树的索引格式

  B树特点：
  1. 所有键值分布在整颗树中
  2. 搜索有可能在非叶子节点结束，在关键字全集内做一次查找，性能逼近二分查找。
  3. 每个节点最多拥有m个子树
  4. 根节点至少有2个子树
  5. 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
  6. 所有叶子节点都在同一层，每个节点最多可以有m-1个key，并且以升序排列。

• B+树

1. 根节点只有1个，分支数量范围[2,m]
2. 除根以外的非叶子节点，每个节点包含分支数范围[[m/2],m]，其中[m/2]表示取大于m/2的最小整数。
3. 所有非叶子节点的关键字数目等于它的分支数量。
4. 所有叶子节点都在同一层，且关键字数目范围是[[m/2],m],其中[m/2]表示取大于m/2的最小整数。
5. 所有非叶子节点的关键字可以看成是索引的部门，这些索引等于其子树(根节点)中的最大（或最小）关键字。
6. 叶子节点包含全部关键字的信息（非叶子节点只包含索引），且叶子节点中的所有关键字依照大小顺序链接（所以一个B+树通常有两个头指针，一个是指向根节点的root，另一个是指向最小关键字的sqt）。