mysql索引结构4种结构_【MySQL】mysql索引结构及其原理

1、定义

索引是一种数据结果，帮助提高获取数据的速度

为了提高查找速度，有很多查询优化算法。但是每种查找算法都只能应用于特定数据结构之上。

索引就是数据库创建的满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据

2、索引数据结构

目前大部分数据库系统及文件系统都采用B Tree或其变种B+Tree作为索引结构

相关概念介绍

B-树(B树)：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

3、为什么使用B Tree(B+Tree)

红黑树也可用来实现索引，但是文件系统及数据库系统普遍采用B/+Tree,为什么？

一般来说，索引本身也很大，不可能全存内存，往往以索引文件的形式存在磁盘

(1)单节点能存储更多数据，使得磁盘IO次数更少。

(2)叶子节点形成有序链表，便于执行范围操作。

(3)聚集索引中，叶子节点的data直接包含数据；非聚集索引中，叶子节点存储数据地址的指针。

4、索引分类

1.普通索引index :加速查找

2.唯一索引

主键索引：primary key ：加速查找+约束(不为空且唯一)

唯一索引：unique：加速查找+约束(唯一)

3.联合索引

-primary key(id,name):联合主键索引

-unique(id,name):联合唯一索引

-index(id,name):联合普通索引

5、聚集索引和非聚集索引

聚集索引和非聚集索引使用的都是B+树结构。

1、非聚集索引

非聚集索引的叶子节点为索引节点，但是有一个指针指向数据节点。

MyISAM是非聚集索引。

2、聚集索引

聚集索引叶子节点就是数据节点。

关于聚集索引，innodb会按照如下规则进行处理：

1，如果一个主键被定义了，那么这个主键就是作为聚集索引

2，如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引

3，如果没有主键也没有合适的唯一索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增。

innodb的普通索引，唯一索引，联合索引都是辅助索引，采用非聚集索引结构。InnoDB的所有辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。