关于大数据:浅谈树形结构的特性和应用上多叉树红黑树堆Trie树B树B树

上篇文章咱们次要介绍了线性数据结构，本篇 233 酱带大家康康 无所不在的非线性数据结构之一：树形构造的特点和利用。

树形构造 ，是指：数据元素之间的关系像一颗树的数据结构。咱们看图谈话：

它具备以下特点：

1. 每个节点都只有无限个子节点或无子节点；
2. 没有父节点的节点称为根节点；
3. 每一个非根节点有且只有一个父节点；
4. 除了根节点外，每个子节点能够分为多个不相交的子树；
5. 树外面没有环路(cycle)

维基百科中列举了计算机科学中树形构造的品种

233 酱当然不会一个个讲，咱们只挑一些相熟的脸孔： 多叉树，二叉树，二叉查找树，红黑树，堆，Trie 树，B 树，B+ 树，LSM Tree，理解他们在对不同规模的数据 增，删，改，查 时所起到的作用就够了。

限于篇幅，本文次要介绍非 LSM Tree 的内容。

多叉树

树体现了一种 继承 的关系，节点之间为父子关系。 多叉树 是指一个父节点能够有多个子节点。也就是：爸爸能够有多个儿子，儿子只能有一个爸爸。

当须要这种分层，继承的场景下均能够思考用树结构来实现，能够简化咱们对数据关系的形容。

此外，节点的每个分支也代表着一种抉择，能够用来做决策。

利用场景：
1.Linux 文件系统
2. 组织关系示意，如公司的组织架构，角色权限零碎等。
3.XML/HTML 数据。
4. 类的继承关系
5. 决策，如游戏中怪物应用的技能抉择，机器学习 …

二叉树

二叉树 （Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构，也就是说 爸爸 最多只能有 两个儿子。

因为计算机利用中存在很多“非黑即白”的场景，同样咱们能够利用 不是走左分支，就是走右分支 这种构造抉择来做一些决策。
另外，利用每个节点下参与方最多为两个，也能够做一些事件。

利用场景：
1. 编译器的语法树结构。
2. 表达式求值和判断：非叶子节点为操作符，叶子节点为数值。
3.Boolean 求值，如（a and b）or (c or d)。
4. 霍夫曼编码
5.IPv4 路由表的存储 …

在咱们的日常开发中，常常须要对数据进行增删改查，每一个步骤的工夫空间效率决定了利用最终的性能。

工夫复杂度 体现在 是否疾速定位到要操作的数据元素，外围在于 索引的好坏；

空间复杂度 体现在 是否占用 更小的内存空间，是否利用计算机各层介质的缓存性能进步访问速度（访问速度：CPU>> 内存 >> 磁盘）。

在以下树形构造的探讨中，心愿小伙伴能多从 索引，所占用内存空间，操作的介质 这些方面思考数据的增删改查性能。

二叉查找树

二叉查找树 （Binary Search Tree）首先是二叉树，同时满足肯定的有序性：节点的左子节点比本人小，节点的右子节点比本人大。

这样当咱们定位一个元素的地位时，从根节点开始查找，小于节点左拐，大于节点右拐。等于节点排序值就刚好找到。二分的索引思维就体现在其中。

利用场景：
二叉查找树的有序性是它可能广泛应用的起因。然而是否高效二分体现在树的高度合理性上。上面要讲的 红黑树 / 堆构造才是其广泛应用。

红黑树

二叉查找树的毛病在于：只限度了节点的有序性，但有序树的结构有好坏。一颗“坏”的有序树间接会被拉成“有序链表”。所以须要通过肯定的条件保障树的平衡性。

树的平衡性 是指整棵树的最高子树和最矮子树相差不大，这样整棵树的高度相对来说低一些，相应的增，删，改，查操作的效率较高较稳固（与树高无关）。

红黑树（Red–black tree）是利用很宽泛的一种均衡树，是面试官的装 X 利器。咱们来看一下它保障平衡性的一些个性：

1. 节点是红色或彩色。
2. 根是彩色。
3. 所有叶子都是彩色（叶子是 NIL 节点）。
4. 每个红色节点必须有两个彩色的子节点。（从每个叶子到根的所有门路上不能有两个间断的红色节点。）
5. 从任一节点到其每个叶子的所有简略门路都蕴含雷同数目的彩色节点。

这些束缚确保了红黑树的要害个性：从根到叶子的最长门路不多于最短门路的两倍长(依据性质 4 和性质 5)。从而整棵树的高度比较稳定，相应的增、删、改、查操作的效率较高较稳固，而不同于一般的二叉查找树。

此外相比其余的均衡树：如高度均衡树 AVL 树，红黑树的增删改效率较高，同时查找性能没有降落很多也比较稳定。所以工业级利用更为宽泛。

利用场景：适宜排序，查找的场景。
1. 容器的根本组成，如 Java 中的 HashMap/TreeMap.
2.Linux 内核的齐全偏心调度器
3.Linux 中 epoll 机制的实现 …

堆

堆是一种非凡的数据结构，它满足两个个性：

1. 堆是一个齐全二叉树；
2. 堆中每一个节点的排序值都必须大于等于（或小于等于）其左右子节点的排序值。

这里解释以下齐全二叉树。它是指：除了最初一层，其余层的节点个数都是满的，最初一层的节点都靠左排列。

这样咱们就能够用数组来存储。

假如根节点在 i = 0 的地位：如果父节点的数组下标为i，则左子节点的数组下标为2 * i+1，右子节点的数组下标为 2 * i + 2。数组比链表的存储益处上篇文章 233 酱提过了，这里就不赘述了。

针对第 2 点，如果每个节点的值都大于等于子树中每个节点值的堆，叫做“大顶堆”。反之叫做“小顶堆”。

堆这种构造绝对有序，且堆顶元素要么最小，要么最大。且利用了 数组和本身个性 增删改查的工夫复杂度较低。

利用场景：
1. 堆排序
2.TopK, 求中位数，求
3. 合并多个有序小文件或汇合
4. 优先队列，如定时工作的存储等 …

Trie 树

Trie 树 又称前缀树或字典树，它是一种专门解决字符串匹配的数据结构，用来解决在一组字符串汇合中疾速查找某个字符串的问题。

它的个性为：

1. 根节点不蕴含字符，除根节点外的每一个子节点都蕴含一个字符。
2. 从根节点到某一节点，门路上通过的字符连接起来，就是该节点对应的字符串。
3. 每个字符串的公共前缀作为一个字符节点保留。

如果咱们有 and,as,at,cn,com 这些关键词，那么构建的 trie 树如下：

Trie 树的实质，就是利用字符串之间的公共前缀，将反复的前缀合并在一起。这样当咱们查找某个字符串时，只须要在 Trie 树上匹配字符串的每个字符，比拟次数仅和 字符串的长度 无关。

然而 Trie 树的毛病就是结构 Trie 树须要很大的内存空间。因为父子字符节点之间用 指针关联。如果用数组保留这些指针，这意味着子节点的数组须要穷举出每一种可能。如子节点字符为 a -z，就须要调配长度为 26 的数组来存储这些可能的子节点。

改良内存调配的措施有：

1. 子节点指针改为用：有序数组、跳表、散列表、红黑树来存储。
2. 子节点合并，如原来 hello 存储为：h->e->l->l->o , 当初可存储为：h->e->llo

Trie 树毕竟比拟节约空间，所以它在字符串的查找中，适宜用于：1. 字符集不能太大 2. 字符串的公共前缀较多 的场景。

利用场景：
1. 关键词匹配，提醒，纠错。
2. 最长公共前缀匹配。
3. 命令主动补全，如 zsh.
4. 网址浏览历史记录。
5. 手机号码簿查问 …

B 树、B+ 树、LSM Tree 是数据库中经常出现的数据结构。对于数据库的增删改查效率，须要思考的首要因素是：磁盘的 IO 拜访次数。

如何缩小 IO 拜访次数？

前文咱们曾经提到了索引，然而 IO 一次不容易，从磁盘中获取数据通常是以块为单位的。如果对于上千万条数据，咱们只建设一层索引构造的话，那索引的数据量也是微小的。

如何升高索引量？

假如咱们到全世界找一个人，咱们是依照 国家 / 省 / 市 / 区 / 街道 / 小区的程序来定位。同理，随着数据量的增大，咱们须要一层层的建设 多级索引。越下层的索引每个块中示意的数据范畴越大。

如何保障咱们建设的多级索引 是“适合”的？

这个适合次要指：存储的数据量大并且树高小。同红黑树一样，咱们须要一些 限度条件 来保障树高。这也就是以下数据结构的限度条件起因了。

B 树

一个 m 阶（该树每个节点最多有 M 个子节点）的 B 树具备以下特色：

1. 根节点至多有两个子女。
2. 每个两头节点都蕴含 k - 1 个元素和 k 个孩子，其中 m/2 <= k <= m
3. 每一个叶子节点都蕴含 k - 1 个元素，其中 m/2 <= k <= m
4. 所有的叶子节点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中 k - 1 个元素正好是 k 个孩子蕴含的元素的值域分划。

一个 3 阶的 B 树插入示意图如下：

利用场景：MongoDB

B+ 树

一个 m 阶的 B + 树具备以下特色：

1. 有 k 个子树的两头节点蕴含有 k 个元素（B 树中是 k - 1 个元素），每个元素不保留数据，只用来索引，所有数据都保留在叶子节点。
2. 所有的叶子节点中蕴含了全副元素的信息，及指向含这些元素记录的指针，且叶子节点自身依关键字的大小自小而大程序链接。
3. 所有的两头节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

看不懂没关系，咱们只须要晓得这些限度条件是为了让 B + 树数据“矮而胖”就好。

这里我间接放张掘金小册《从根儿上了解 MYSQL》B+ 树主键索引的示意图：

利用场景
1.Mysql InnoDB 存储引擎。

看到这里常考面试题来了：B 树和 B + 树有什么区别？为什么 Mongo 用 B 树？为什么 Mysql 用 B + 树？

B 树 vs B+ 树

看图谈话，B 树 和 B+ 树显著不同的中央是：
1.B 树非叶子节点即是索引，也是数据；B+ 树非叶子节点仅是索引，数据全副存储在叶子节点。
2.B+ 树叶子节点的数据之间是用链表链接的。
这会导致：

B+ 树相比 B 树：
1. 数据的连续性：

• B+ 树叶子节点上一页存储的数据是间断的，当须要一个结点上的数据时，B+ 树能够增大缓存的命中率。

2. 叶子结点之间的连接性：

• 当作范畴或全文扫描时，B+ 树能够依赖叶子结点做线性程序扫描，而 B 树只能在每一层的结点上做扫描。B+ 树同样能够增大缓存的命中率。

B 树相比 B + 树：
当作繁多数据查问时，B 树的结点均匀离根结点更近，均匀查问效率比 B + 树快。

总结一下：B+ 树相比 B 树，前者更适宜范畴查问，后者更适宜繁多数据查问。

Mongo 是非关系型数据库，数据之间的关系用嵌套解决。它的次要应用场景是：谋求 单个读写记录的性能。

Mysql 是关系型数据库，数据之间的关系用独特的索引键，Join 解决。它的应用场景：不仅存在大量的繁多数据查问，也存在大量的范畴查问。

所以下面的问题能够简略扯一扯了吧。

下篇文章 233 酱筹备介绍近几年数据库中经常出现的角色：LSM Tree。感觉本文有播种 or 期待下篇 请四连 【关注，点赞，在看，转发】 反对下 233 吧～

参考资料：
[1]. 维基百科
[2].https://www.youtube.com/watch?v=OJ5NYq1Eii8
[3].https://time.geekbang.org/column/article/72414
[4].https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c
[5].https://draveness.me/whys-the-design-mongodb-b-tree/