mysql 索引类型

一.二叉搜索树、B-树、B+树、B*树之间的关系

1.二叉搜索树

特点：
   1.所有非叶子结点至多拥有两个儿子（Left和Right）；
   2.所有结点存储一个关键字；
   3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

搜素规则：
    (1).从根结点开始，查询的关键字与结点的关键字相等，那么就命中；        
    (2).查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；
    (3).如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

二叉树与二分查找联系：
    (1).如果二叉搜索树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；
    (2).比连续内存空间的二分查找的优点: 改变二叉搜索树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

2.二叉树的平衡算法由来

上述图四也是二叉搜索树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；

因此，使用二叉搜索树还要考虑尽可能让B树保持图三的结构，且避免图四的结构，即“平衡”问题；      
实际使用的二叉搜索树都是在原二叉搜索树的基础上加上平衡算法，即“平衡二叉树”；
如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；
平衡算法是一种在二叉搜索树中插入和删除结点的。

3.B树 即 B-树

多路搜索树（并不是二叉的）：
   1.定义任意非叶子结点最多只有M个儿子；且M>2；
   2.根结点的儿子数为[2, M]；
   3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
   4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
   5.非叶子结点的关键字个数=指向儿子的指针个数-1；
   6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
   7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
   8.所有叶子结点位于同一层；

搜素规则：
    (1).从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，
    (1).否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B-树的特性：
    (1).关键字集合分布在整颗树中；
    (2).任何一个关键字出现且只出现在一个结点中；
    (3).搜索有可能在非叶子结点结束；
    (4).其搜索性能等价于在关键字全集内做一次二分查找；
    (5).自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

解释：其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

结论：B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
   由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

4.B+树

B+树是B-树的变体，也是一种多路搜索树,其定义基本与B-树同，除了
  1.非叶子结点的子树指针与关键字个数相同；
  2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
  3.为所有叶子结点增加一个链指针；
  4.所有关键字都在叶子结点出现；

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

 B+的特性：
   1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
   2.不可能在非叶子结点命中；
   3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
   4.更适合文件索引系统；

5.B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

6.总结

(1).二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
(2).B（B-）树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
(3).B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
(4).B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

二.MySQL索引类型详解

1.存储方式区分

根据存储方式的不同，MySQL 中常用的索引在物理上分为  B-树索引和 HASH 索引两类，两种不同类型的索引各有其不同的适用范围。

1) B-树索引

B-树索引又称为 BTREE 索引，目前大部分的索引都是采用 B-树索引来存储的。

B-树索引是一个典型的数据结构，其包含的组件主要有以下几个：
    叶子节点：包含的条目直接指向表里的数据行。叶子节点之间彼此相连，一个叶子节点有一个指向下一个叶子节点的指针。
    分支节点：包含的条目指向索引里其他的分支节点或者叶子节点。
    根节点：一个 B-树索引只有一个根节点，实际上就是位于树的最顶端的分支节点。

基于这种树形数据结构，表中的每一行都会在索引上有一个对应值。
因此，在表中进行数据查询时，可以根据索引值一步一步定位到数据所在的行。

B-树索引可以进行全键值、键值范围和键值前缀查询，也可以对查询结果进行 ORDER BY 排序。但 B-树索引必须遵循左边前缀原则，要考虑以下几点约束：
    查询必须从索引的最左边的列开始。
    查询不能跳过某一索引列，必须按照从左到右的顺序进行匹配。
    存储引擎不能使用索引中范围条件右边的列。

2) 哈希索引

哈希（Hash）一般翻译为“散列”，也有直接音译成“哈希”的，就是把任意长度的输入（又叫作预映射，pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

哈希索引也称为散列索引或 HASH 索引。MySQL 目前仅有 MEMORY 存储引擎和 HEAP 存储引擎支持这类索引。其中，MEMORY 存储引擎可以支持 B-树索引和 HASH 索引，且将 HASH 当成默认索引。

HASH 索引不是基于树形的数据结构查找数据，而是根据索引列对应的哈希值的方法获取表的记录行。

哈希索引的最大特点是访问速度快

MySQL 需要读取表中索引列的值来参与散列计算，散列计算是一个比较耗时的操作。

哈希索引的最大特点是访问速度快，但也存在下面的一些缺点：
    MySQL 需要读取表中索引列的值来参与散列计算，散列计算是一个比较耗时的操作。也就是说，相对于 B-树索引来说，建立哈希索引会耗费更多的时间。
    不能使用 HASH 索引排序。
    HASH 索引只支持等值比较，如“=”“IN()”或“<=>”。
    HASH 索引不支持键的部分匹配，因为在计算 HASH 值的时候是通过整个索引值来计算的。

2.逻辑区分

根据索引的具体用途，MySQL 中的索引在逻辑上分为以下 5 类：

1) 普通索引

普通索引是 MySQL 中最基本的索引类型，它没有任何限制，唯一任务就是加快系统对数据的访问速度。
普通索引允许在定义索引的列中插入重复值和空值。

创建普通索引时，通常使用的关键字是 INDEX 或 KEY。
    例 1
    下面在 tb_student 表中的 id 字段上建立名为 index_id 的索引。
    CREATE INDEX index_id ON tb_student(id);

2) 唯一索引

唯一索引与普通索引类似，不同的是创建唯一性索引的目的不是为了提高访问速度，而是为了避免数据出现重复。
唯一索引列的值必须唯一，允许有空值。如果是组合索引，则列值的组合必须唯一。

创建唯一索引通常使用 UNIQUE 关键字。
    例 2
    下面在 tb_student 表中的 id 字段上建立名为 index_id 的索引，SQL 语句如下：
    CREATE UNIQUE INDEX index_id ON tb_student(id);

其中，id 字段可以有唯一性约束，也可以没有。

3) 主键索引

顾名思义，主键索引就是专门为主键字段创建的索引，也属于索引的一种。

主键索引是一种特殊的唯一索引，不允许值重复或者值为空。

创建主键索引通常使用 PRIMARY KEY 关键字。不能使用 CREATE INDEX 语句创建主键索引。

4) 空间索引

空间索引是对空间数据类型的字段建立的索引，使用 SPATIAL 关键字进行扩展。

创建空间索引的列必须将其声明为 NOT NULL，空间索引只能在存储引擎为 MyISAM 的表中创建。

空间索引主要用于地理空间数据类型 GEOMETRY。对于初学者来说，这类索引很少会用到。
    例 3
    下面在 tb_student 表中的 line 字段上建立名为 index_line 的索引，SQL 语句如下：
    CREATE SPATIAL INDEX index_line ON tb_student(line);

其中，tb_student 表的存储引擎必须是 MyISAM，line 字段必须为空间数据类型，而且是非空的。

5) 全文索引

全文索引主要用来查找文本中的关键字，只能在 CHAR、VARCHAR 或 TEXT 类型的列上创建。在 MySQL 中只有 MyISAM 存储引擎支持全文索引。

全文索引允许在索引列中插入重复值和空值。

不过对于大容量的数据表，生成全文索引非常消耗时间和硬盘空间。

创建全文索引使用 FULLTEXT 关键字。
    例 4
    在 tb_student 表中的 info 字段上建立名为 index_info 的全文索引，SQL 语句如下：
    CREATE FULLTEXT INDEX index_info ON tb_student(info);

其中，index_info 的存储引擎必须是 MyISAM，info 字段必须是 CHAR、VARCHAR 和 TEXT 等类型。

3.实际使用区分

索引在逻辑上分为以上 5 类，但在实际使用中，索引通常被创建成单列索引和组合索引。

1）单列索引

单列索引就是索引只包含原表的一个列。在表中的单个字段上创建索引，单列索引只根据该字段进行索引。

单列索引可以是普通索引，也可以是唯一性索引，还可以是全文索引。只要保证该索引只对应一个字段即可。=
    例 5
    下面在 tb_student 表中的 address 字段上建立名为 index_addr 的单列索引，address 字段的数据类型为 VARCHAR(20)，索引的数据类型为 CHAR(4)。SQL 语句如下：
    CREATE INDEX index_addr ON tb_student(address(4));

这样，查询时可以只查询 address 字段的前 4 个字符，而不需要全部查询。

2）多列索引

组合索引也称为复合索引或多列索引。相对于单列索引来说，组合索引是将原表的多个列共同组成一个索引。多列索引是在表的多个字段上创建一个索引。该索引指向创建时对应的多个字段，可以通过这几个字段进行查询。但是，只有查询条件中使用了这些字段中第一个字段时，索引才会被使用。

例如，在表中的 id、name 和 sex 字段上建立一个多列索引，那么，只有查询条件使用了 id 字段时，该索引才会被使用。
    例 6
    下面在 tb_student 表中的 name 和 address 字段上建立名为 index_na 的索引，SQL 语句如下：
    CREATE INDEX index_na ON tb_student(name,address);

该索引创建好了以后，查询条件中必须有 name 字段才能使用索引。
提示：一个表可以有多个单列索引，但这些索引不是组合索引。一个组合索引实质上为表的查询提供了多个索引，以此来加快查询速度。比如，在一个表中创建了一个组合索引(c1，c2，c3)，在实际查询中，系统用来实际加速的索引有三个：单个索引(c1)、双列索引(c1，c2)和多列索引(c1，c2，c3)。