«

MySql索引数据结构以及存储引擎

晨曦 发布于 阅读：62 Mysql

MySql索引数据结构：
1.二叉树
2.红黑树
3.Hash表
4.B-Tree
二叉树（Binary Search Tree）：

存储结构：每个结点最多有两个子树的树结构。子树通常被称为“左子树”（left subtree）和“右子树”（right subtree）。

1.若左子树不空，则左子树上所有结点的值均小于它的根结点的值
2.若右子树不空，则右子树上所有结点的值均大于它的根结点的值
3.左、右子树也分别为二叉排序树
4.没有键值相等的结点




缺点：查询次数多，I/O操作频繁，需从第一个节点往后进行比较，查询效率慢

红黑树（RED/BLACK TREE）：

存储结构：二叉查找树，也称为平衡二叉树。

相比于二叉树：查询次数减少，比二叉树查询次数少一半

缺点：红黑树的高度在数据量大时不可控，查询叶子节点时，I/O操作次数也多。

Hash表（Hash Table）：

存储结构：维护一个Hash表，以列值计算Hash值，把Hash值和磁盘文件的地址维护到Hash表中，查找时只需进行一次I/O操作。

缺点：范围查询时需全表扫描。

B-TREE：

存储结构：多路平衡树，设定树的高度。

1.叶节点具有相同的深度
2.叶节点的指针为空
3.节点中的数据索引从左到右递增排列

缺点：区间查找问题

B+TREE（B-TREE变种）：

存储结构：Mysql使用B+Tree实现索引

1.非叶子节点不存储data，只存储索引，可以放更多索引
2.叶子节点不存储指针
3.顺序访问指针，提高区间访问的性能


MyISAM存储引擎：

索引文件和数据文件分离（非聚集索引）。

非聚集索引：存放引用地址

.FRM .MYD 存储索引表字段值 .MYI存储索引数据值对应引用地址
InnoDB存储引擎：

表数据文件本身按B+Tree组织的一个索引文件

聚集索引：叶节点包含完整的数据记录

.FRM .ibd存储索引数据

Mysql