B 树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B 树中，所有记录节点都是按照键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。
B 树 索引的本质就是B 树在数据库中的实现。 B 索引在数据库中有一个特点是高扇出性，因此在数据库中，B 树的盖度一般都在 2~4层，这也就是说查找某一键值的行记录时最多只需要 2到4次IO， 这倒不错。因为当前一般的机械硬盘每秒至少可以做100次IO，2~4 次的IO意味查询时间只需 0.02 ~ 0.04 秒。
数据库中的B 树索引可以分为:
聚集索引 (clustered index) 和辅助索引 (secondary index)，内部都是B 树，即高度平衡。
聚集索引与辅助索引不同的是:
叶子节点存放的是否是一整行的信息。
一 MyISAM索引实现
1. 主键索引
MyISAM引擎使用B 树作为索引结果，叶节点的data域存放的是数据记录的地址。下图为MyISAM表的主索引，Col1为主键。
2. 辅助索引
在MyISAM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。下图在Col2上建立一个辅助索引
同样也是一颗B Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
二 InnoDB索引实现
1 主键索引
同样是B 树，实现方式却完全不同。InnoDB表数据文件本身就是一个索引结构，树的叶节点data域保存了完整的数据记录，这种索引叫做聚集索引。
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键(MyISAM可以没有)，如果没有显式指定，则mysql会自动选择一个可以唯一标识数据记录的列作为主键。如果不存在这种列，则mysql自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
2 辅助索引
辅助索引（Secondary Index，也称为非聚集索引）.
InnoDB的所有辅助索引都引用主键作为data域。下图为定义在Col3上的一个辅助索引
辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引也会包含主键列，所以如果主键定义的比较大，其他索引也将很大。InnoDB 不会压缩索引。
不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B Tree，非单调的主键会造成在插入新记录时数据文件为了维持B Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
辅助索引的叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。书签就是相应行数据的聚集索引键（主键）。
当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。
参考资料
https://blog.csdn.net/biggoodloong/article/details/98886082
Kotlin 开发者社区
国内第一Kotlin 开发者社区公众号，主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。
Kotlin 开发者社区
