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索引的数据构造是啥的具体内容，更多请关注百分百源码网其它相关文章！