本文非小马原创，为学习总结笔记，作为日后复盘回顾，感谢原作者分享，文末已注明出处，侵删。
MySQL中索引实现的原理是什么？目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。在 MySQL 中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的。
树，二叉树（从左到右垂直有序），平衡二叉树（左右高度限制），b树，b+树，完全二叉树，堆（上下每一层大小是有序的，左右大小无序），大根堆，小根堆。
一、MyISAM 索引实现
MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 域存放的是数据记录的地址。我们借用两张图来说明。
MyISAM 的索引方式也叫做“非聚集索引”,之所以这么称呼是为了与 InnoDB的聚集索引区分。意思是，索引中只保存着数据在表中的地址而不是保存数据本身。
二、InnoDB 索引实现
InnoDB 也使用 B+Tree 作为索引结构,但具体实现方式却与 MyISAM 截然不同。InnoDB 的数据文件本身就是索引文件。从上文知道,MyISAM 索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB 中,表数据文件本身就是按 B+Tree 组织的一个索引结构,这棵树的叶点data 域保存了完整的数据记录。这个索引的 key 是数据表的主键,因此 InnoDB 表数据文件本身就是主索引。
借用两张图来说明。
InnoDB 主索引(同时也是数据文件),可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。
三、总结
myisam中主键索引和辅助索引都是记录数据在表中的地址，索引比较小，但查询数据都需要二次查找。先根据索引找到数据地址再通过地址查找到表中的数据。
innodb主键索引是聚簇的，索引树中直接记录了表数据，占空间比较大。辅助索引是非聚簇的，这和上面myisam一样。啥意思呢？主键索引的查找只需要一次查找直接拿到数据，非主键的索引查找需要二次查找。所以主键索引会比较快。
彩蛋1：对于innodb而言，表没有主键可以吗？
可以，但是如果没有主键，就是属于辅助索引，要多查一次索引。不过mysql会拿唯一键来自动创建为隐藏的主键索引，所以如果是对唯一键条件查询，其实没有主键也不会多一次查找。因为聚簇索引具有唯一性，由于聚簇索引是将数据跟索引结构放到一块，因此一个表仅有一个聚簇索引。聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一且非空的索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键（类似oracle中的RowId）来作为聚簇索引。聚簇索引是唯一的，InnoDB一定会有一个聚簇索引来保存数据。非聚簇索引一定存储有聚簇索引的列值。
InnoDB聚簇索引选择顺序：
默认选择主键；
没有主键，选择唯一的非空索引；
都没有，则隐式定义一个主键；
非聚簇索引，数据存储和索引分开，叶子节点存储对应的行，需要二次查找，通常称为[二级索引]或[辅助索引]。
彩蛋2：count函数会引起全表扫描吗？
InnoDB：count(主键) 全表扫描累加，count(1)全表扫描累加，count(字段)分为字段可为空和字段不可为空，不可为空则读到后累加，可为空则读到后判断不为空累加。count(*) 不取值累加。除了 count(*)外其他都要取值基本上 count(*)是最快的。
MyISAM： 会记录一张表的行数，count 时直接返回行数。
彩蛋3：我们经常在DB工具中创建索引时选择索引类型除了Btree还有个哈希类型?
是的。哈希类型的优点：哈希表这种结构适用于只有等值查询的场景，新增方便。缺点：非有序，做区间查询的速度是很慢，需要全部遍历！！哈希索引也不支持多列联合索引的最左匹配规则！！
参考文献：
