前言

嗨喽，大家好，我是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 ：树有三种遍历形式，别离为 前序、中序、后序 ，依据具体需要应用不同的遍历形式

如果是二叉树呢？

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

解答了你的一点点小纳闷后，咱们回到正题，还是聊聊二叉树的事。

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

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

上述展现了MySQL的数据生吞活剥放到二叉树中玩法，但你发现没？咱们仍旧无奈防止树被全副遍历的问题。

思考

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

问题一：树和二叉树（N叉树）都无奈防止遍历整棵树，那下一篇要讲的均衡二叉树为什么能够做到只须要遍历“半棵树”？

问题二：工夫复杂度的示意形式 O(1) O(n) O(log2^n) 别离代表什么？

致谢

感激你看到这里，2021 我会在思否公布本人电商设计的录播课，也是我首个录播课。

心愿本篇文章能够帮忙到你，谢谢。