Mysql索引 - B树/B+树
介绍
Mysql支持多种存储引擎，每种存储引擎对索引的支持也是不一样的， Mysql数据库支持的索引包括B树 哈希索引 全文索引 本文主要介绍最常用的B树
B树/B+树介绍
B树
《算法导论》对B树定义 - B树是平衡树的一种，主要用于操作存储在磁盘等二级存储设备上的大量数据。相比起内存（主存）来说，磁盘操作的速度非常慢（慢几个数量级），所以涉及到存储在磁盘的数据的时候，尽量减少磁盘的读取和写入操作对于提高操作速度是非常重要的。B树就是针对这个特点进行设计以满足相应要求的。 我们知道二叉树的查找时间复杂度是O(log2N)与树的深度相关，所以减少树的深度就能提高查找速度，B树时间复杂度是O(logdN) 其中d就是树的深度所以d越大时间就越短
B+树
B+树 是B树的变种 他也是Mysql中使用的数据结构 , 一颗B+树包含根节点，内部节点，和叶子节点。它相对于B树有一下几个不同点:
更适合文件索引系- 内节点不存储data,只存储key,叶子节点不存储指针
- 每个节点的指针上限为2d而不是2d+1
- 所有的关键字都在叶子节点出现
- B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
MylSAM 索引
MylSAM引擎用B+树作为索引的数据结构，叶节点的data域存放的是数据的地址，也叫做非聚集索引
InnoDB 索引
InnoDB 也是用B+树作为数据结构，但是与MylSAM不同是，叶子节点的data域存放的是数据本身，相对的叫做聚集索引，InnoDB的辅助索引都引用主键作为data域，所以这也是不建议使用过长的字段作为主键，因为所有辅助索引都引用主键，过长的索引会另辅助索引变得过大，因为InnoDB是一颗B+树，如果主键不是单调的话，频繁插入更新会导致B+树频繁更新调整，造成碎片