mysql索引结构原理
第一部分：基础知识
第二部分：MYISAM和INNODB索引结构
1、 简单介绍B-tree B+ tree树
2、 Myisam索引结构
3、 innodb索引结构
4、 Myisam索引与InnoDB索引相比较
第一部分：基础知识：
索引
官方介绍索引是帮助MySQL高效获取数据的数据结构。笔者理解索引相当于一本书的目录，通过目录就知道要的资料在哪里，不用一页一页查阅找出需要的资料。关键字index
唯一索引
强调唯一，就是索引值必须唯一，关键字unique index
创建索引：
1、create unique index 索引名 on 表名(列名);
2、alter table 表名 add unique index 索引名 (列名);
主键
主键就是唯一索引的一种(同时注意键和索引在概念上的区别)，主键要求建表时指定，一般用auto_increatment列，关键字是primary key
主键创建：creat table test2 (id int not null primary key auto_increment);
全文索引
InnoDB不支持，Myisam支持，可在 CHAR、VARCHAR 或 TEXT 列上创建。
Create table 表名( id int not null primary anto_increment,title,varchar(100),FULLTEXT(title))type=myisam
单列索引与多列索引
索引可以是单列索引也可以是多列索引（也叫复合索引）。按照上面形式创建出来的索引是单列索引，现在先看看创建多列索引：
create table test3 (id int not null primary key auto_increment,uname char(8) not null default '',password char(12) not null,INDEX(uname,password))type=myisam;
注意：INDEX(a, b, c)可以当做a或(a, b)的索引来使用，但和b、c或(b,c)的索引来使用这是一个最左前缀的优化方法，在后面会有详细的介绍，你只要知道有这样两个概念
聚集索引
一种索引，该索引中键值的逻辑顺序决定了表中相应行的物理顺序。 聚集索引确定表中数据的物理顺序。Mysql中myisam表是没有聚集索引的，innodb有（主键就是聚集索引），聚集索引在下面介绍innodb结构的时有详细介绍。
查看表的索引
通过命令：Show index from 表名
如：mysql> show index from test3;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+----+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part |
Packed | Null | Index_type | Comment |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+----+
| test3 | 0 | PRIMARY | 1 | id | A | 0 | NULL |
NULL | | BTREE | |
Table：表名
Key_name：什么类型索引（这里是主键）
Column_name：索引列的字段名
Cardinality：索引基数，很关键的一个参数，平均数值组=索引基数/表总数据行，平均数值组越接近1就越有可能利用索引
Index_type：如果索引是全文索引，则是fulltext,这里是b+tree索引，b+tree也是这篇文章研究的重点之一
第二部分：MYISAM和INNODB索引结构
1、 简单介绍B-tree B+ tree树
B-tree结构视图
一棵m阶的B-tree树，有以下性质
（1）Ki 表示关键字值，上图中，k1<k2<…<ki<k0<Kn(可以看出，一个节点的左子节点关键字值<该关键字值<右子节点关键字值)
（2）Pi 表示指向子节点的指针，左指针指向左子节点，右指针指向右子节点。即是：p1[指向值]<k1<p2[指向值]<k2……
（3）所有关键字必须唯一值（这也是创建myisam 和innodb表必须要主键的原因），每个节点包含一个说明该节点多少个关键字，如上图第二行的i和n
（4）节点：
每个节点最可以有m个子节点。
根节点若非叶子节点，至少2个子节点，最多m个子节点
每个非根，非叶子节点至少[m/2]子节点或叫子树（[]表示向上取整），最多m个子节点
（5）关键字：
根节点的关键字个数1~m-1
非根非叶子节点的关键字个数[m/2]-1~m-1,如m=3，则该类节点关键字个数：2-1~2
（6）关键字数k和指向子节点个数指针p的关系：
k+1=p ，注意根据储存数据的具体需求，左右指针为空时要有标志位表示没有
B+tree结构示意图如下：
B+树是B-树的变体，也是一种多路搜索树：
非叶子结点的子树指针与关键字个数相同
为所有叶子结点增加一个链指针（红点标志的箭头）
2、 Myisam索引结构
MyisAM索引用的B+tree来储存数据，MyisAM索引的指针指向的是键值的地址，地址存储的是数据，如下图：
（1）结构讲解：
上图3阶树，主键是Col2，Col值就是改行数据保存的物理地址，其中红色部分是说明标注。
1标注部分也许会迷惑，前面不是说关键字15右指针的指向键值要大于15，怎么下面还有15关键字？因为B+tree的所以叶子节点包含所有关键字且是按照升序排列（主键索引唯一，辅助索引可以不唯一），所以等于关键字的数据值在右子树
2标注是相应关键字存储对应数据的物理地址，注意这也是之后和InnoDB索引不同的地方之一
2标注也是一个所说MyiAM表的索引和数据是分离的，索引保存在”表名.MYI”文件内，而数据保存在“表名.MYD”文件内，2标注的物理地址就是“表名.MYD”文件内相应数据的物理地址。（InnoDB表的索引文件和数据文件在一起）
辅助索引和主键索引没什么大的区别，辅助索引的索引值是可以重复的（但InnoDB辅助索引和主键索引有很明显的区别，这里先提醒注意一下）
3.innodb索引结构
（1）首先有一个表，内容和主键索引结构如下两图：
col1 col2 col3 1 15 phpben 2 20 mhycoe 3 23 phpyu 4 25 bearpa 5 40 phpgoo 6 45 phphao 7 48 phpxue
结构上：由上图可以看出InnoDB的索引结构很MyisAM的有很明显的区别
MyisAM表的索引和数据是分开的，用指针指向数据的物理地址，而InnoDB表中索引和数据是储存在一起。看红框1可一看出一行数据都保存了。
还有一个上图多了三行的隐藏数据列（虚线表），这是因为MyisAM不支持事务，InnoDB处理事务在性能上并发控制上比较好，看图中的红框2中的DB_TRX_ID是事务ID，自动增长；db_roll_ptr是回滚指针，用于事务出错时数据回滚恢复；db_row_id是记录行号，这个值其实在主键索引中就是主键值，这里标出重复是为了容易介绍，还有的是若不是主键索引（辅助索引），db_row_id会找表中unique的列作为值，若没有unique列则系统自动创建一个。
(2)假如上表中Col1是主键，而Col2是辅助索引，则相应的辅助索引结构图：
可以看出InnoDB辅助索引并没有保存相应的所有列数据，而是保存了主键的键值（图中1、2、3….）这样做利弊也是很明显：
在已有主键索引，避免数据冗余，同时在修改数据的时候只需修改辅助索引值。
但辅助索引查找数据事要检索两次，先找到相应的主键索引值然后在去检索主键索引找到对应的数据。这也是网上很多mysql性能优化时提到的“主键尽可能简短”的原因，主键越长辅助索引也就越大，当然主键索引也越大。
4、MyisAM索引与InnoDB索引相比较
MyisAM支持全文索引（FULLTEXT）、压缩索引，InnoDB不支持
innoDB支持事务，MyisAM不支持
MyisAM顺序储存数据，索引叶子节点保存对应数据行地址，辅助索引很主键索引相差无几；AnnoDB主键节点同时保存数据行，其他辅助索引保存的是主键索引的值;
MyisAM键值分离，索引载入内存（key_buffer_size）,数据缓存依赖操作系统；InnoDB键值一起保存，索引与数据一起载入InnoDB缓冲池;
MyisAM主键（唯一）索引按升序来存储存储，InnoDB则不一定;
MyisAM索引的基数值（Cardinality，show index 命令可以看见）是精确的，InnoDB则是估计值。这里涉及到信息统计的知识，MyisAM统计信息是保存磁盘中，在alter表或Analyze table操作更新此信息，而InnoDB则是在表第一次打开的时候估计值保存在缓存区内
MyisAM处理字符串索引时用增量保存的方式，如第一个索引是‘preform’，第二个是‘preformance’，则第二个保存是‘7，ance‘，这个明显的好处是缩短索引，但是缺陷就是不支持倒序提取索引，必须顺序遍历获取索引
附：mysql查询流程
