引言
索引数据结构对比
二叉树
左边子节点的数据小于父节点数据，右边子节点的数据大于父节点数据。如果col2是索引，查找索引为89的行元素，那么只需要查找两次，就可以获取到行元素所在的磁盘指针地址。
如果col1是索引，查找索引为6的行元素，那么需要查找六次，就可以获取到行元素所在的磁盘指针地址，即得到了该索引为6的行元素。因此二叉树不适合存储单边增长的序列字段，近乎全表扫描获取数据。
红黑树
本质二叉树，属于二叉平衡树，jdk1.8 的底层实现；存储大数据量，树的高度不可控， 数量越大，树的高度越高；500w行数据，2的n次方=500w数据量， n是树的高度，也就是查询次数；
hash表
通过散列可以快速获取磁盘文件指针，对于指定索引查找文件非常快，但是对于范围查找没法支持。
B树
本质是多路二叉树；叶节点具有相同的深度，叶节点的指针为空；所有索引元素不重复；节点中数据索引从左到右依次递增的；
B+树（B树的变种）
非叶子节点不存储数据数据库 索引 数据结构 深入理解Mysql索引底层数据结构与算法，背后的故事，只存储索引(冗余)和指针，可以放更多的索引，树高降低 ；叶子节点包含所有索引字段；叶子节点比b树增加了指针连接；叶子节点有双向指针链接(首尾子节点还通过指针连接)，提高区间访问的性能，范围查找；
为什么mysql页文件默认16K？
MySQL每个B+树节点最大存储容量：16KB （指针+数据+索引）。假设我们一行数据大小为1K，那么一页就能存16条数据，也就是一个叶子节点能存16条数据；再看非叶子节点，假设主键ID为类型，那么长度为8B，指针大小在源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)那么一颗高度为2的B+树能存储的数据为：=18720条，一颗高度为3的B+树能存储的数据为：*16=（千万级条）
show like ``复制代码
因此，B+树存储大数据量的表也可以非常高效的获取数据，MySQL使用B+树作为索引的数据结构。
存储引擎
存储引擎最终作用于：表 ，不是数据库在mysql的安装的根目录下，有一个data目录，里面存放的是所有表的数据。
frm文件：存储这张表的表结构MYD文件：存储这张表的所有数据行MYI文件：存储这张表的索引字段
表数据文件本身是按照B+tree组织的一个索引结构文件frm文件：存储这张表的表结构ibd文件：存储这张表的所有数据行和索引字段聚集(聚簇)索引----叶节点包含完整数据记录
为什么表必须有主键，并且推荐使用整型的自增主键？
为什么非主键索引结构叶子节点存储的是主键值？
联合索引
定义联合索引(员工级别，员工姓名，员工出生年月)，将联合索引按照索引顺序放入节点中，新插入节点时，先按照联合索引中的员工级别比较，如果相同会按照是员工姓名比较，如果员工级别和员工姓名都相同 最后是员工的出生年月比较。可以从图中从上到下，从左到右看，第一个B+树的节点 是通过联合索引的员工级别比较的数据库 索引 数据结构，第二个节点是 员工级别相同数据库 索引 数据结构，会按照员工姓名比较，第三个节点是 员工级别和员工姓名都相同，会按照员工出生年月比较。
小结
欢迎关注头条号:JAVA大飞哥
点击关注评论转发一波：私信小编发送“架构”（免费获取）
获取微服务、分布式、高并发、高可用，性能优化丶Mysql源码分析等等一些技术资料
最后，每一位读到这里的Java程序猿朋友们，感谢你们能耐心地看完。希望在成为一名更优秀的Java程序猿的道路上，我们可以一起学习、一起进步！都能赢取白富美，走向架构师的人生巅峰!
点击关注不迷路