|
一、简介 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索引的数据结构是什么的详细内容，更多请关注模板之家(www.mb5.com.cn)其它相关文章！ |
