共计 2869 个字符,预计需要花费 8 分钟才能阅读完成。
前言
嗨喽,大家好,我是 CrazyCodes, 近一年写的文章,都是一些广度方面的思考,新的一年,在技术深度上也须要有更多的摸索,感激各位的继续反对!
MySQL
先聊聊大家熟知的 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`;
对数据进行查问
看到这里,你可能说了,这是在讲什么,增删改查都是常识,有什么好讲的,那咱们当初就正式进入正题,首先从插入记录开始说起,MySQL 会应用 B + 树来存储数据记录,B+ 树是 B 树的延长,而 B 树又是均衡二叉树的延长,除了均衡二叉树还有二叉查找树,顺次基于其概念延长的排序,大略是如下这样
B+ 树 -> B 树 -> 均衡二叉树 -> 二叉查找树 -> 二叉树 -> 树
当然也不仅仅是所有跟树无关的数据结构,这里为了进步学习树这种数据结构的趣味,所以以 MySQL 讲起,纠其本源,再联合 MySQL 的数据记录将这一串常识链接起来,那咱们把这个程序倒过去顺次讲起
树 -> 二叉树 -> 二叉查找树 -> 均衡二叉树 -> B 树 -> B+ 树
我尽量不把这些数据结构讲成教科书的样子。
树????
你要不晓得树是什么玩意,就别持续看上来了????,就是大巷上咱们看到的树,大巷的树也就是咱们常识认知的树,是通过“树根”、“树枝”和“树叶”组成,缺一样,这树也不是一颗残缺的树。
那么数据结构中的树指的什么,你能够把手机或者电脑倒过去看上图,数据结构中的树,就是一个倒过去的树,并不是他非要倒过去能力说,而是依据人类失常的视觉与思维,就例如你看书总不能从最初一页的最初一个字开始从后往前读把,倒过去只是便于了解和浏览它罢了。
在数据结构中倒过去的树大略是张上面这个样子
倒树
正树
正树、倒树,都贴出来了,你能够尝试比照这两张图,看看那张图更容易了解,接下来的案例只会以倒树展现。
树是其余树型数据结构的根底,这里你必须要熟记一些基本概念
- 树根,树的根节点
- 子节点,树枝一、二、三是树根的子节点
- 兄弟节点,树枝一、二、三互为兄弟节点
- 父节点,树根是树枝一的父节点,树枝一是树枝 1 - 1 的父节点
置信依据上图多看几遍,这很容易了解
那咱们生吞活剥,把 MySQL 的数据放到这个最简略的树中
这是我随便摆放的,当然你想怎么摆就怎么摆,例如
这看起来像跟棍,或者
无论怎样,咱们创立了一个树,那依据 SQL 语句
SELECT * FROM `user`;
咱们须要查到根节点,这很简略,而后去判断根节点的左子节点是否有值,有的话取出来,右子节点也是一样的情理,这就是所谓的树的遍历。那么咱们当初在 SQL 上加些条件
SELECT * FROM `user` WHERE `id` = 1;
那这个条件,在树结构中如何查呢,到这里,你会发现一个问题
无论条件是什么,咱们都须要遍历整棵树,遍历树的深度,齐全取决于要查问的数据所在的地位,地位靠前,就少遍历些,地位靠后就多遍历下。
这里讲一个更根底的常识,工夫复杂度,工夫复杂度用于示意某个算法所计算的工夫长度,那咱们依据下面这个例子,能够剖析出其均匀工夫复杂度为 O(n) , 当然最好的状况是 O(1) , 这种状况就是根节点就是咱们要找的数据。
数据的一直减少,才使得咱们无奈持续应用最原始的数据结构,哎,都是数据逼得呀。
假如咱们不仅仅有 3 条记录,而是在 3000 万条查找 Join, 凑巧还是第 3000 万条,那么如果应用最根本的树结构去查问的话,那么咱们将要进行 3000 万去查问才能够取得最终后果。是不是感觉不切实际了?
其实这样的话,是不是树结构都不重要了,他能够是一个 数组、链表或者队列等等,能够用任意数据结构去存储,当然每种数据结构的呈现都有其存在的起因。那么咱们应用原始树的构造感觉不靠谱,那么追随我的文字来到二叉树的世界!
二叉树
二叉树,顾名思义是只有两个叉的树,每个节点只有两个叉,这是它的个性,这时候你就疑难了,为啥不能是三叉树,四叉树,N 叉树呢?当然能够有,那么咱们举一个例子,咱们再往 user 表内插几行数据
INSERT INTO `user` VALUES(4,"Jorr");
INSERT INTO `user` VALUES(5,"Queie");
INSERT INTO `user` VALUES(6,"Kioa");
当初咱们库里有 6 条记录
咱们拿三叉树举例
我把每个节点须要查问的次数列个表,这里我应用前序遍历树的形式,让你简略的分明树有几叉意味着什么
tips:树有三种遍历形式,别离为 前序、中序、后序,依据具体需要应用不同的遍历形式
节点 | 次数 |
---|---|
1,join | 1 |
3,jeein | 2 |
5,queie | 3 |
6,kioa | 4 |
2,tom | 5 |
4,jorr | 6 |
如果是二叉树呢?
节点 | 次数 |
---|---|
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 我会在思否公布本人 电商设计 的录播课,也是我首个录播课。
心愿本篇文章能够帮忙到你,谢谢。