概述
索引是对数据库表中一列或多列的值进行排序的一种结构, 使用索引可快速访问数据库表中的特定信息.
索引数据结构
二叉树
二叉树 (binary tree) 是指树中节点的度不大于 2 的有序树, 它是一种最简单且最重要的树. 二叉树的递归定义为: 二叉树是一棵空树, 或者是一棵由一个根节点和两棵互不相交的, 分别称作根的左子树和右子树组成的非空树; 左子树和右子树又同样都是二叉树
对于数组 {1,2,3,4,5} 数据结构将成为了链表
特点:
父节点下面有两个子节点.
右边节点的数据大于左边节点的数据.
二叉树. PNG
红黑树
红黑树是一种特定类型的二叉树, 它是在计算机科学中用来组织数据比如数字的块的一种结构. 若一棵二叉查找树是红黑树, 则它的任一子树必为红黑树.
红黑树是一种平衡二叉查找树的变体, 它的左右子树高差有可能大于 1, 所以红黑树不是严格意义上的平衡二叉树(AVL), 但对之进行平衡的代价较低, 其平均统计性能要强于 AVL .
由于每一棵红黑树都是一棵二叉排序树, 因此, 在对红黑树进行查找时, 可以采用运用于普通二叉排序树上的查找算法, 在查找过程中不需要颜色信息.
红黑树数据结构如下图:
红黑树数据结构. PNG
特点:
红黑树是每个结点都带有颜色属性的二叉查找树, 颜色或红色或黑色.
结点是红色或黑色.
根结点是黑色.
所有叶子都是黑色.(叶子是 NIL 结点)
每个红色结点的两个子结点都是黑色.(从每个叶子到根的所有路径上不能有两个连续的红色结点)
从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点.
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长. 结果是这个树大致上是平衡的. 因为操作比如插入, 删除和查找某个值的最坏情况时间都要求与树的高度成比例, 这个在高度上的理论上限允许红黑树在最坏情况下都是高效的, 而不同于普通的二叉查找树.
是性质 4 导致路径上不能有两个连续的红色结点确保了这个结果. 最短的可能路径都是黑色结点, 最长的可能路径有交替的红色和黑色结点. 因为根据性质 5 所有最长的路径都有相同数目的黑色结点, 这就表明了没有路径能多于任何其他路径的两倍长.
因为红黑树是一种特化的二叉查找树, 所以红黑树上的只读操作与普通二叉查找树相同.
B-Tree
叶子结点具有相同的深度, 叶节点的指针为空
所有元素不重复
节点中的数据索引从左到右边递增排列
B 树数据结构. PNG
B+Tree
非叶子结点不存储数据, 只存储索引(冗余), 可以存放更多的索引
叶子结点包含所有索引字段
叶子结点用指针链接, 提高区间访问的性能(可以提升范围查找的效率)
B + 树数据结构. PNG
特点关键字: 节点内有序, 叶子结点指针链接, 非叶子结点存储索引(冗余)
查询 MySQL 索引的数据页的大小:
- MySQL> show global status like 'Innodb_page_size';
- +------------------+-------+
- | Variable_name | Value |
- +------------------+-------+
- | Innodb_page_size | 16384 |
- +------------------+-------+
为什么设置 16kb 呢?
Hash
对索引的 key 进行一次 hash 计算就可以定位出数据存储的位置
很多的时候 hash 索引要比 B+ 树索引更高效
仅能满足 "=" , "in" 不支持范围查询
存在 hash 冲突问题
Hash 数据结构. PNG
索引
InnoDB 索引实现(聚集)
表数据文件本身就是按 B+Tree 组织的一个索引结构文件
聚集索引 - 叶子节点包含了完整的数据记录
为什么 InnoDb 表必须有主键, 并且推荐使用整型的自增主键?
如果没有设置索引的话, MySQL 会选择一个数据唯一的列作为主键索引, 如果找不这样的列. 会去做创建一个隐藏列类似 rowid.
表数据文件按照 B+Tree 的数据结构维护, 在叶子节点维护的是该行的数据. 所以必须有主键.
整型更方便 B+Tree 排序, 自增的话, 对于数据结构的存放更快, 顺序存放, 不需要进行大量树的平衡操作.
为什么非主键索引结构叶子节点的存储的是主键值?
一致性, 让主键索引先成功, 然后再去更新非主键索引关系
节省存储空间.
主键索引示意图:
InnoDB 索引实现. PNG
非主键索引示意图
如果查询的是通过 name = Alice 去查询的时候:
走非主键索引去查询, 查询完后拿到信息(Alice, 18). 其实这里也是一个非聚簇索引
然后进行回表查询, 再次通过主键去查询做回表查询.
两个数据文件:
.frm 主要是存储表结构信息
.ibd 主要是存储索引和数据
MyISAM 索引文件(非聚集)
索引文件和数据文件是分离的(非聚集)
MyISAM 存储引擎索引. PNG
三个数据文件:
.frm 数据结构文件
.myd 文件主要是存储数据
.myi 文件主要是存储索引信息
聚集索引和非聚集索引
特征:
聚集 / 非聚集主要是索引文件是否和数据文件在一起.
查询效率上来说聚集索引不会跨文件查询效率会更加快.
联合 / 复合索引
多个字段组织成一个共同的索引
组合索引. PNG
最左前缀原理为什么这样来使用?
索引的数据是被排序的, 如果跳过字段的话是无法被使用的.
示例:
where name = 'Jeff' and age = 22 -- 命中索引
where age = 30 and postatin='manager' -- 不命中索引
where postation = 'dev' -- 不命中索引
参考资料
百度百科
来源: http://database.51cto.com/art/202110/685312.htm