首页 / MYSQL / mysql索引的数据结构是什么
mysql索引的数据结构是什么
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了mysql索引的数据结构是什么,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2128字,纯文字阅读大概需要4分钟。
内容图文
一、简介
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索引的数据结构是什么的详细内容,更多请关注Gxl网其它相关文章!
内容总结
以上是互联网集市为您收集整理的mysql索引的数据结构是什么全部内容,希望文章能够帮你解决mysql索引的数据结构是什么所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。