登录  /  注册

mysql索引的数据结构是什么

步履不停
发布: 2019-06-14 10:34:34
原创
11419人浏览过

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索引的数据结构是什么的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
相关标签:
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号