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.顺序访问指针,提高区间访问的性能
索引文件和数据文件分离(非聚集索引)。
非聚集索引:存放引用地址
.FRM .MYD 存储索引表字段值 .MYI存储索引数据值对应引用地址
InnoDB存储引擎:
表数据文件本身按B+Tree组织的一个索引文件
聚集索引:叶节点包含完整的数据记录
.FRM .ibd存储索引数据