Mysql Innodb的索引结构:B+ Tree 聚簇

索引

索引（Index）是帮助MySQL高效获取数据的数据结构。
MongoDb索引使用BTree，而Mysql的MyISAM和Innodb使用B+Tree,为什么？

mySQL 使用B+Tree

B+Tree是一种适应文件系统而产生的一种BTree的变形树，其数据全部存储在叶子节点，而非叶子节点只存储占用空间很小的索引。
这样在以页为单位的索引中可以存放更多的节点，减少了磁盘IO,提高了效率。

MySQL的MyISAM存储引擎使用B+Tree的非聚集索引，B+Tree的叶子节点上的data，并不是数据本身，而是数据存放的地址。
而InnoDB存储引擎使用B+Tree的聚集索引，InnoDB的主键是聚簇索引。

聚簇索引 (聚集索引)

一些地方区分聚簇索引和聚集索引，这里笔者倾向于两者是同一个意义,英文都是：clustered index。

聚簇索引就是物理地址连续存放的索引。在读取区间的时候查找速度非常快，相应的更新速度会受到影响。

InnoDB存储引擎的主键是聚簇索引。而MyISAM的主键仅仅只是一个叫做PRIMARY的唯一、非空的索引。

当表有聚簇索引时，它的数据行实际上存放在索引的叶子页(leaf page)中。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。

• MyISAM可以没有主键，InnoDB必须有主键，不设置会InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引，如果还是没有则会生成隐藏的主键。

• 术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起

二级索引(辅助索引/非聚簇索引)

二级索引存储的是记录的主键，而不是数据存储的地址。唯一索引、普通索引、前缀索引等都是二级索引。

稠密索引

索引项对主表中的所有条目建立索引。聚簇索引是密集索引。
叶子节点保存的不只是键值，还保存了位于同一行记录里的其他列的信息，由于密集索引决定了表的物理排列顺序，一个表只有一个物理排列顺序，所以一个表只能创建一个密集索引

稀疏索引

索引项只对主表中的部分记录(即不会给每条记录)建立索引。 InnoDB的非主键（即非聚簇）及MyISAM都是稀疏索引。
稀疏索引所占空间小，并且插入和删除时所需维护的开销也小。但可能一次定位不到。

其他 Hash索引、全文索引

1. MySQL的Memory存储引擎使用Hash索引
   hash 索引不能比较范围，不能排序，不能实现前缀索引
   适合小数据量（大了会发生hash碰撞）内存中使用。Btree比较适合磁盘。

2. 全文索引(myISAM的char、varchar和text的字段上)，v5.6.24后的InnoDb
   MySQL的全文索引适合英文文本，对中文支持不是很好，如有需要用ES类的全文检索工具。

3. 前缀索引，索引的时候选择前面几个字符作为索引即可。