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.顺序访问指针,提高区间访问的性能

MyLsam存储引擎:

索引文件和数据文件分离(非聚集索引)。

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

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

InnoDB存储引擎:

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

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

.FRM .ibd存储索引数据