mysql索引的数据结构是什么【MySQL教程】,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索引的数据构造是什么的细致内容,更多请关注ki4网别的相干文章!