共计 1170 个字符，预计需要花费 3 分钟才能阅读完成。
索引数据结构
1、二叉搜寻树（Binary Search Tree）
二叉搜寻树是每个节点最多有两个子节点的树，依照右侧子节点大于本节点，左侧子节点小于本节点的法则排列，能够用作搜寻，构造如下图所示
二叉树尽管能够用于查找，但在某种特定状况下查找效率并不高，相似于下图：
2、红黑树
对于二叉树的毛病，红黑树是一种领有 自均衡 属性的二叉树，红黑树有五个个性：
- 每个结点是彩色或者红色。
- 根结点是彩色。
- 每个叶子结点（NIL）是彩色。[留神 ：这里叶子结点，是指为空(NIL 或 NULL) 的叶子结点！不是有值的最初一个节点。]
- 不能有两个相连的红色节点。
- 每个结点到叶子结点 NIL 所通过的彩色结点的个数一样的。
依据以上五种属性，红黑树生成时采纳左旋，右旋，左右旋，右坐旋等才做，会生成出一颗绝对均衡的二叉树，如下图
3、Hash 表
Hash 表相似于 java 中的 hashMap，把索引列做 hash 映射后以 KV 构造存储在内存中，是精准查找最快的索引构造，只须要一次 hash 便能够定位，但不反对范畴查找。
就是个 K - V 构造，不画图了
4、B-Tree
因为数据库要存储大量的数据，如果采纳二叉树进行查找，数据量过大时二叉树的层级过多，须要由上到下进行查找效率过慢，所以呈现了 B -Tree，BTree 有如下特色
·叶节点具备雷同的深度
·叶节点的指针为空
·所有索引元素不反复
·节点中的数据索引从左到右递增排列
数据结构间接上图
5、B+Tree
不过 mysql 真正采纳的不是 BTree，Btree 在做索引的时候有些中央并不是很实用，最终优化出了 B +tree 作为 mysql innoDB 存储类型的索引，B+tree 的特色如下
- 非叶子节点不存储 data，只存储索引(冗余)
- 能够放更多的索引
- 叶子节点蕴含所有索引字段
- 叶子节点用指针连贯，进步区间拜访的性能
构造如下图
PS：innoDB 中的主键索引的 B +tree 是汇集索引，叶子结点间接存储的其余字段的值，用于缩小 IO 的次数，而辅助索引的叶子结点则是存储的主键的值，用于辅助查找
mysql 次要索引类型
1：MyISAM 存储引擎索引实
MyISAM 的索引和数据文件是离开的（非汇集索引），索引的叶子节点存储的是数据的物理地址，查找到相干索引后再用索引去硬盘上查找数据
2：InnoDB 存储引擎索引实现
InnoDB 的索引是和数据存储在一起的（汇集索引），叶子结点中存储了所有其余字段的值，只须要一次加载叶子结点的 IO 进行索引匹配，匹配胜利后不须要再次进行 IO 操作读取对应的数据
– 表数据文件自身就是按 B +Tree 组织的一个索引构造文件
– 非主键索引构造叶子节点存储主键值的起因是为了一致性和节俭存储空间
3：联结索引的底层存储构造
联结索引是依据索引建设时字段的排列程序建设的索引，后续索引是对第一个字段索引的再划分，差找时如果不能保障依照索引简历时的程序进行查问，则联结索引生效
