mysql索引的数据构造有哪些
一、简介
mysql索引的数据构造是树,常用的存储引擎innodb采纳的是B+Tree。这里对B+Tree及其相干的
查寻树进行简要介绍。
二、各种查寻树
1、二叉排序树(也称为二叉查寻树)
二叉排序树是最简略的查寻树,特色:
a)是一棵二叉树;
b)左子树所有结点的值小于它的父结点的值,右子树所有结点的值大于它的父结点的值。
2、均衡二叉树(又称AVL树)
均衡二叉树是二叉排序树的根基上,对树的深度进行了限定,从而减少了查寻比拼的次数,
特色:
a)是一棵二叉树;
b)左子树所有结点的值小于它的父结点的值,右子树所有结点的值大于它的父结点的值;
c)左子树与右子树的深度差在-1、0、1内,不然对子树进行扭转调整。
3、B-树(B-Tree)
B-树是多路均衡查寻树,相关于均衡二叉树,对父结点的直接子结点个数,不再仅限于2,
可以指定m(自定义),这样可以在树的深度不批量添加的条件下,保留更多的结点。
B-树是平常在文件系统中运用。
特色:
a)树的每个结点最多有m(自定义)子结点;
b)若根结点不是叶子结点,则至少有两个子结点;
c) 除根结点外的所有非叶子结点,至少有m/2上取整个子结点;
d)父结点下的最左边子树所有结点的值均小于父结点最小值,
最右侧子树所有结点的值均大于父结点最大值,
其余中间子树所有结点的值则介于指针的父结点两边的值;
e)所有叶子结点都在统一层;
注意:所有结点均带有值
4、B+树(B+Tree)
B+树是B-树变体,相关于B-树,叶子结点的值包括了所有的值,所有父结点的值是反复了叶子结点的值,
父结点只起索引查寻的作用,同时所叶子结点也也形成了一条有序的链表。
mysql中存储引擎为innodb的索引,采纳的数据构造便是B+树。
特色:
a)有m个子结点的父结点就有m个关键字;
b)所有叶子结点包括了所有关键字(值),且形成由小到大的有序链表;
c) 所有非叶子结点起索引作用,结点仅包括子树所有结点的最大值;
d)所有叶子结点都在统一层;
注意:叶子结点包括了所有的关键字(值)。
5、B*树(B*Tree)
B*树是B+树的变体,相对B+树,添加了对统一层非叶子结点的指针,即统一层非叶子结点也形成了一条链表。
三、总结
综上,上述各种查寻树是彼此关联的。
归结到mysql中innodb索引,采纳的是B+树,如聚簇索引,是通过主键来汇集数据,采纳B+树实现,
这便是一种索引,也是mysql的一种数据存储构造,叶子结点包括了所有的数据,非叶子结点仅起索引作用(若
没有定义主键,则innodb会隐式定义一个主键来作为聚簇索引)。
更多MySQL的相干技术文章,请拜访MySQL教程栏目进行学习!
以上就是mysql索引的数据构造有哪些的细致内容,更多请关注 百分百源码网 其它相干文章!