索引：“其实我是一种数据结构”_索引是一种数据结构吗?

“人家真的 不是目录”

引言

大家好，我是索引，在MySQL中你可以使用CREATE INDEX indexName ON table_name (column_name)或alter table table_name add index(column_name)来创造我！在这里我主要澄清一下，我不是目录，你可以认为我是一种排序的数据结构，实在不行你就把我当存指针的文件也行但是我真的不是目录。

索引概述

常见的索引有：主键索引、唯一索引、普通索引和全文索引。
索引能够在海量数据的查找中大大加快检索速率，提高系统性能。这个过程不用加内存、不用改程序、不用调sql，索引真是物美价廉！德才兼备！

索引的创建

创建主键索引：

//直接加primery key即可自动生成索引
create table user1(id int primery key,name varchar(10));
//一个表中最多只能有一个主键，不可为null，key值不能重复
1
2
3

创建唯一索引：

//直接加unique即可自动生成索引
create table user1(id int primery key,name varchar(10) unique);
//一张表中可以有多个unique索引
//不能重复
//如果在一个unique上指定not null等价于主键索引
1
2
3
4
5

创建普通索引：

alter table table_name add index(column_name);
//一个表中可以有多个普通索引，可支持重复值
1
2

鉴于全文索引要求引擎必须是MyISAM，已退出历史舞台，此处不表。

索引的删除

drop index index_name on table_name;
1

索引的查询

explain查询有无索引

mysql> explain select * from articles where body like '%database%'\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: articles
type: ALL
possible_keys: NULL
key: NULL -- null表示没有用到索引，'%database'当然不会用到啦
key_len: NULL
ref: NULL
rows: 6
Extra: Using where
1 row in set (0.00 sec)
1
2
3
4
5
6
7
8
9
10
11
12
13

show keys查询何种索引

show keys from teble_name;
show index from table_name;
desc table_name;
1
2
3

mysql> show keys from goods\G
*********** 1. row ***********
Table: goods <= 表名
Non_unique: 0 <= 0表示唯一索引
Key_name: PRIMARY <= 主键索引
Seq_in_index: 1
Column_name: goods_id <= 索引在哪列
Collation: A
Cardinality: 0
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE <= 以二叉树形式的索引
Comment:
1 row in set (0.00 sec)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

索引的原理

B树、B+和Hash。
索引的数据结构类型和引擎相关，innodb默认的索引数据结构是B+树。

1. 哈希索引（哈希果然果然是我的本命数据结构，会迟到但绝不会缺席在任何为难我的地方）。其本质是哈希散列，所以适合查询单条记录，在使用哈希索引时，数据库字段中的数据转换成定长的hash值，与这条数据的行指针一起存入哈希表对应的位置，哈希冲突由链地址法解决。
2. B树和B+树索引。
   innoDB只支持这两种索引方式。我们先来看看这二者的定义和结构：
   B树的定义：B树可以看作是对2-3查找树的一种扩展，是一种绝对平衡树，这意味着根节点到叶子节点的长度是固定的，IO的读写次数是可控的，这也是为什么不用红黑树等其它数据结构的原因。

B树要求：
每个节点最多 3 个子节点;
除了跟节点和叶节点，其他节点至少有2个子节点； 根节点如果不是叶节点，至少有2个子节点；
非叶节点中关键字数量n， 则 2 <= n <= 3;

B树的结构是（其实有page）：
B树可以在内部节点存储键和值，因此对可能存在频繁访问的数据，建议采用B树。但显然，B树不适合遍历。
B+树： B+ 树是 B 树的一种变体，也是一种多路平衡查找树， 它和 B 树主要不同点在：

每个节点最多含有 m 个关键字；
所有的叶节点中包含了全部关键字信息，以及指向还有这些关节字记录的指针，且叶节点本身按照关键字顺序相互连接；
所有非叶节点可以看成是索引部门，节点中仅包含其子树中最大关键字。

换而言之，相较于B树，B+树是只在叶节点存放数据的，叶子节点之间使用链表的形式串起来。这大大提高了遍历的效率，节省了空间和IO次数，尤其是在使用where进行范围查找的时候。
B+树还有一个很好的点，即在满足聚簇索引时无需回表。
说起回表。。。。首先还是看什么是聚簇索引吧。。。

聚簇索引

聚簇索引将数据存储与索引放在了一起，找到了索引也就找到了数据。

显然，innode使用的是聚簇索引，由MySQL自动创建。MyISAM则是非聚簇索引，它将索引和数据分开放入两个文件。聚簇索引是自动创建的，如果有primary或者unique则会按其创建一个主键/唯一聚簇索引，如果没有，mysql也会自动生成一个隐藏的聚簇索引，并按照聚簇索引排序。

辅助索引

如果将普通列作为where查询条件，将无法走索引而是走全表扫描，这是非常不合算的，由此，提出了辅助索引。
辅助索引是建立在聚簇索引的基础上的，在查询时，会把主键索引和辅助索引的列单独拿出来，形成新表，按照辅助列进行排序建立新的磁盘块并以辅助索引的列名做索引。在查询时，如果辅助索引中有要查的列，则取出数据，如果没有，则返回主键索引搜索，这个动作称为回表。

联合索引

使用多个字段同时建立一个索引，如果想要查询（命中）索引，需要按照建立索引时的字段挨个查询。

索引存在的问题

天下没有白吃的午餐，索引的查询效率如此之高是以增删改的效率为代价的，在数据库中进行每一次的增删改都会重新创建索引，因此，不必要的索引会大大降低数据库的性能。
其次，对于海量数据的删除应当先删除索引，然后删除无用的数据，再创建新的索引才是正道。（毕竟直接删除万一中断，然后回滚。。。）
最后，瑕不掩瑜，索引依旧是提高数据库查询效率的首选。