数据库索引

数据库索引.md

MySQL 5.5之前版本默认的存储引擎是MyISAM，5.5之后，MySQL默认的存储引擎是InnoDB。 MyISAM使用B-Tree实现主键索引、唯一索引和非主键索引。 InnoDB中非主键索引使用的是B-Tree(B树)数据结构，而主键索引使用的是B+Tree。

B树的出现所要解决的问题是：在进行大量数据的操作中，不可能一下子将数据都读进内存。因此频繁的对磁盘进行读写，I/O读写速度严重的影响了性能，B树正是为了减少对磁盘的读写次数。

以下是一个5阶B树，叶子节点没有画出，叶子节点将指向记录：

由于网上对此的解释都比较拗口且术语都用的不一致，对于新手比较难以理解，以下将使用更加通俗的语言解释。

首先图中每一串数字块都是一个节点，每个数字叫做一个关键字。

B树或者是一个空树，或者就要满足以下条件：

• 不严谨的说，所有节点 都拥有数个子节点，其中的最大个数就是这个B树的阶。

• 子节点个数限制：一个m阶B树，每个节点最多有m个子节点。而最少则情况不一样，根节点最少有两个子节点，叶子节点自然没有子节点，其余节点至少要ceil(m/2)个节点（ceil指向上取整）

• 关键字限制： 一个节点有n-1个关键字则它就有n个子节点（这个n也必定符合上一条的限制，也就是说关键字的个数被子节点个数所限制，即m阶B树除了根节点，最少需要ceil(m/2)-1个关键字），并且n个关键字按照递增排序。

• 节点的结构为：n 　k1 　k2 ... kn　　

  　　　　　　　p0 　p1 　p2 ... pn
  n为关键字个数，k1kn是关键字。p0pn是指向子节点的指针，且满足pn所指子节点中的关键字最大值小于kn+1.最小值大于kn，po与pn自然只需满足一半的条件。

• 所有节点中的关键字都不相等。

• 所有叶子节点必须在同一层，可以用空指针补空位。

B+树相较于B树区别在于：

• 所有实际数据都在叶子节点，其余节点的用途只是用来索引而不储存实际数据。也就是说B树的所有节点如果不插入重复数据的话，则所有节点不会有重复值。而B+树必定有重复值。
• 所有叶子节点会从小到大形成一个链表。
• 如果是叶子节点，则p0~pn-1指向记录，pn指向邻节点

对于插入删除操作不是本章描述重点略微叙述，以B+树为例：

• 当叶子节点中的关键字数没有达到上限直接插入。

• 如果达到上限，进行对半分裂，必须满足关键字最小个数的要求，并且把前半部分最大值复制到父节点中（这需要3次磁盘访问）。

• 如果父节点关键字数目达到上限，则在进行分裂，并且把前半部分最大值复制到父节点中。

• 当叶子节点中的关键字数没有达到下限直接删除。

• 如果达到下限，将从邻节点借一个关键字过来，这个关键字也复制为父节点中的关键字。

• 如果借完以后邻节点关键字个数低于下限，则合并节点，变为一个满关键字的节点，父节点的关键字减少一个。

• 如果父节点的关键字减少一个后关键字个数低于下限，重复上述过程。

基本概念

• 顺序索引：基于值的顺序排列
• 散列索引：基于将值平均分布到若干散列桶中
• 搜索码：用于在文件中查找记录上的属性（集）称为搜索码，其中每一个取值叫做搜索码值。

顺序索引

每个索引结构与一个搜索码相关联，顺序索引按照顺序存储搜索码的值，并将该搜索码与其对应的记录关联。
如果文件的记录的物理顺序按照某个搜索码指定的顺序排列，那么该搜索码对应的索引称为聚集索引或主索引。
如果文件的记录的物理顺序按与某个搜索码指定的顺序不同，那么该搜索码对应的索引称为非聚集索引或辅助索引。
在搜索码上有聚集索引的文件称为索引顺序文件。（聚集索引不是一定在搜索码上么？为什么要加 在搜索码上）。
索引项或索引记录是指由一个 搜索码值 和 指向对应这个搜索码值的一条或多条记录的 指针构成。
稠密索引：每个搜索码值都有一个索引项。
稀疏索引: 部分搜索码有一个索引项，易知只有聚集索引才能使用，因为聚集索引是顺序的。如果非顺序就会找不到没有索引项的记录。

可以拥有的组合： 聚集稠密索引、聚集稀疏索引、 非聚集稠密索引。

静态散列

桶表示能存储一条或多条记录的一个存储单位，通常一个桶就是一个磁盘快，当然也可能不是。
用K表示所有搜索码值的集合，用B表示所有的桶地址的集合，散列函数h是一个从K到B的集合。
与其他数据结构的散列类似，根据散列函数查到对应的桶，查找、删除同样如此。

散列文件组织

通过计算搜索码值上的一个散列函数直接获得包含该记录的磁盘块(桶)地址。
桶的总数的一个典型值是1.2倍的预估满数据桶。
如果产生桶溢出，闭地址法使用溢出桶形成链表一个不够就再加一个当然这会对算法有轻微的改动。开地址法可以使用常用的线性探测法或者再散列进同一个桶，但会比较麻烦，数据库系统一般使用前者。

散列索引组织

将散列函数作用于搜索码值获得对应的桶，在桶中放入搜索码值本身以及相关联的指针（一个码可能有多个指针）。

术语散列索引 来表示散列文件结构或者辅助散列索引。严格的说散列索引只是一种辅助索引结构，散列索引从来不需要作为聚集索引结构来使用。因为聚集散列索引就表示记录存储的顺序就是按照散列存储，即散列文件结构。

索引命中

单个索引

• 如果使用索引但是所扫描的数据仍旧需要全表的30%左右，则不会使用索引。（例如区分度不大的索引，不等号等）
• or的前后需要都有索引才会使用索引，可以使用union代替。

联合索引

总体来说遵循索引的最左原则。(也就是说联合索引中的索引有顺序关系,因此在创建联合索引的时候需要注意顺序）。

• 语句中使用联合索引中的全部索引，可以命中索引。
• 语句中连续使用联合索引中的前面的索引，可以命中索引。
  例如联合索引顺序a1、a2、a3, 在sql语句中使用了关于a1、a3的条件则a3不会使用索引，使用关于a2、a3的条件则都不会使用索引。
• 使用or不会命中索引。因为联合索引中顺序不是最前面的那个索引顺序不是连续的所以不使用索引，而因为又是or所以都不使用索引。
• 在分组和排序（groupby、order）中,如果顺序和联合索引顺序一样（不必从最左开始）,则可以利用索引的有序特性。
• or条件需要涉及的所有column都加上索引才会命中索引。
• where子句中like查询如果以%开头，索引不会命中，以%结尾则会。但如果select中直接选了这个了列，则就不会有问题。
• 列是字符串类型，数据需要使用引号引起来，否则不会使用索引。

查看是否命中

可以在mysql中使用explain SQL语句进行查看。更详细的可以使用navicat软件查看。

执行结果：

select_type	table	partitions	type	possible_keys	key	key_len	ref	row	filtered	extra
查询类型	输出结果的表	分区	访问方式	可能使用的索引	实际所使用的索引	索引长度	使用哪个列或常数与索引一起使用	查询的行数	命中率	查询的详细信息

• select_type:SIMPLE:简单表。Primary:主查询，最外层的查询。UNION:第二个或后面的查询语句。SUBQUERY：子查询中的第一个select。
• type:越往右性能越好

ALL	index	range	ref	eq_ref	const,system	null
全表扫描	索引全扫描，遍历整个索引	索引范围扫描	使用联合索引的最左前缀join多表	使用主键或唯一非空索引进行join多表	只有一条可以匹配	直接得到结果