欢迎光临
我们一直在努力

从MySQL开始聊聊“树”结构 (上)前言MySQL树🌲二叉树思考致谢

image.png

前言

嗨喽,大家好,我是CrazyCodes, 近一年写的文章,都是一些广度方面的思考,新的一年,在技术深度上也需要有更多的探索,感谢各位的持续支持!

MySQL

image.png

先聊聊大家熟知的MySQL,我们使用MySQL肯定是有数据存储的需求。

我们从基础开始看,首先我们创建一张用户表

CREATE TABLE `user` (
  `id` int unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(32) COLLATE utf8mb4_general_ci DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_general_ci;

这是一张简单的用户表,包含id和name两个字段,id为主键自增,name上没有索引。想必大家对索引都有一定的认识,索引是一种数据结构,即本篇的核心议题“树”结构,索引可以达到快速命中某条记录,“快速”一词代表着在时间和空间相结合的最优解,当然也并不代表索引越多,数据表设计越合理,要根据实际业务去选择。

我们随机向表中插入几条记录

INSERT INTO `user` VALUES(1,"Join");
INSERT INTO `user` VALUES(2,"Tom");
INSERT INTO `user` VALUES(3,"Jeein");

按照预期,数据库内出现三条对应的记录,这里我使用语句

SELECT * FROM `user`;

对数据进行查询
image.png
看到这里,你可能说了,这是在讲什么,增删改查都是常识,有什么好讲的,那我们现在就正式进入正题,首先从插入记录开始说起,MySQL会使用B+树来存储数据记录,B+树是B树的延伸,而B树又是平衡二叉树的延伸,除了平衡二叉树还有二叉查找树,依次基于其概念延伸的排序,大概是如下这样

B+树 -> B树 -> 平衡二叉树 -> 二叉查找树 -> 二叉树 -> 树

当然也不仅仅是所有跟树有关的数据结构,这里为了提高学习树这种数据结构的兴趣,所以以MySQL讲起,纠其根源,再结合MySQL的数据记录将这一串知识链接起来,那我们把这个顺序倒过来依次讲起

树 -> 二叉树 -> 二叉查找树 -> 平衡二叉树 -> B树 -> B+树

我尽量不把这些数据结构讲成教科书的样子。

树🌲

image.png
你要不知道树是什么玩意,就别继续看下去了😂,就是大街上我们看到的树,大街的树也就是我们常识认知的树,是通过“树根”、“树枝”和“树叶”组成,缺一样,这树也不是一颗完整的树。

那么数据结构中的树指的什么,你可以把手机或者电脑倒过来看上图,数据结构中的树,就是一个倒过来的树,并不是他非要倒过来才能说,而是根据人类正常的视觉与思维,就例如你看书总不能从最后一页的最后一个字开始从后往前读把,倒过来只是便于理解和阅读它罢了。

在数据结构中倒过来的树大概是张下面这个样子

倒树
image.png

正树
image.png

正树、倒树,都贴出来了,你可以尝试对比这两张图,看看那张图更容易理解,接下来的案例只会以倒树展示。

树是其他树型数据结构的基础,这里你必须要熟记一些基本概念

  • 树根,树的根节点
  • 子节点,树枝一、二、三是树根的子节点
  • 兄弟节点,树枝一、二、三互为兄弟节点
  • 父节点,树根是树枝一的父节点,树枝一是树枝1-1的父节点

相信根据上图多看几遍,这很容易理解

那我们生搬硬套,把MySQL的数据放到这个最简单的树中
image.png
这是我随意摆放的,当然你想怎么摆就怎么摆,例如
image.png
这看起来像跟棍,或者
image.png
无论怎样,我们创建了一个树,那根据SQL语句

SELECT * FROM `user`;

我们需要查到根节点,这很简单,然后去判断根节点的左子节点是否有值,有的话取出来,右子节点也是一样的道理,这就是所谓的树的遍历。那么我们现在在SQL上加些条件

SELECT * FROM `user` WHERE `id` = 1;

image.png

那这个条件,在树结构中如何查呢,到这里,你会发现一个问题

无论条件是什么,我们都需要遍历整棵树,遍历树的深度,完全取决于要查询的数据所在的位置,位置靠前,就少遍历些,位置靠后就多遍历下。

这里讲一个更基础的知识,时间复杂度,时间复杂度用于表示某个算法所计算的时间长度,那我们根据上面这个例子,可以分析出其平均时间复杂度为 O(n) , 当然最好的情况是 O(1) , 这种情况就是根节点就是我们要找的数据。

数据的不断增加,才使得我们无法继续使用最原始的数据结构,哎,都是数据逼得呀。

假设我们不仅仅有3条记录,而是在3000万条查找Join,恰巧还是第3000万条,那么如果使用最基本的树结构去查询的话,那么我们将要进行3000万去查询才可以获得最终结果。是不是感觉不切实际了?

其实这样的话,是不是树结构都不重要了,他可以是一个数组、链表或者队列等等,可以用任意数据结构去存储,当然每种数据结构的出现都有其存在的原因。那么我们使用原始树的结构感觉不靠谱,那么跟随我的文字来到二叉树的世界!

二叉树

image.png

二叉树,顾名思义是只有两个叉的树,每个节点只有两个叉,这是它的特性,这时候你就疑问了,为啥不能是三叉树,四叉树,N叉树呢?当然可以有,那么我们举一个例子,我们再往user表内插几行数据

INSERT INTO `user` VALUES(4,"Jorr");
INSERT INTO `user` VALUES(5,"Queie");
INSERT INTO `user` VALUES(6,"Kioa");

现在我们库里有6条记录
image.png
我们拿三叉树举例
image.png
我把每个节点需要查询的次数列个表,这里我使用前序遍历树的方式,让你简单的清楚树有几叉意味着什么

tips :树有三种遍历方式,分别为 前序、中序、后序 ,根据具体需求使用不同的遍历方式

节点 次数
1,join 1
3,jeein 2
5,queie 3
6,kioa 4
2,tom 5
4,jorr 6

如果是二叉树呢?
image.png

节点 次数
1,join 1
3,jeein 2
5,queie 3
6,kioa 4
2,tom 5
4,jorr 6

有没有很奇怪?无论几叉,查询4,jorr数据都需要6次,感觉用哪个都一样是不?并不是这样,你可以这样考虑一个问题,在使用程序去遍历这两棵树时,二叉树需要判断左右子节点,而三叉树则需要判断左中右三个节点,他们所在的内存空间不同,专业点说,他们的空间复杂度不同。

解答了你的一点点小疑惑后,我们回到正题,还是聊聊二叉树的事。

二叉树分为完全二叉树和不完全二叉树

  • 完全二叉树代表每个节点都有2个树枝(就是不缺胳膊少腿)
  • 不完全二叉树反之就是(缺胳膊少腿),某个树叉上可能只有左子树,没有右子树

上述展示了MySQL的数据生搬硬套放到二叉树中玩法,但你发现没?我们依旧无法避免树被全部遍历的问题。

思考

我将在下一篇文章讲述剩余的“几颗树”,这里我给你留一道思考题。

问题一:树和二叉树(N叉树)都无法避免遍历整棵树,那下一篇要讲的平衡二叉树为什么可以做到只需要遍历“半棵树”?

问题二:时间复杂度的表示方式 O(1) O(n) O(log2^n) 分别代表什么?

致谢

感谢你看到这里,2021 我会在思否发布自己电商设计的录播课,也是我首个录播课。

希望本篇文章可以帮助到你,谢谢。

https://segmentfault.com/a/1190000039245060

赞(0)
未经允许不得转载:ITyet » 从MySQL开始聊聊“树”结构 (上)前言MySQL树🌲二叉树思考致谢
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址