心中有“树”！图文并茂介绍数据结构中常见的树（二）

计算机科学家尼古拉斯·沃斯（Niklaus Wirth）曾说过：编程=数据结构+算法 ，可见数据结构在编程中的重要性。

50 年过去了，计算机行业日新月异，大佬的这句名言是否还适用于当下？使用成熟且丰富的框架已经可以完成绝大部分任务的今天，基础的数据结构的知识，是否还有用武之地？

今天，我们继续上一章的话题，聊一聊数据结构中的树（Tree），在实际的编程中应用场景。

大家好，我是不会写代码的纯序员——Chunel Feng，很高兴又在这里跟各位绅士们见面了。在上一章中，我们介绍了 6 种常见的树结构（BST，AVL，RB Tree，Trie Tree、Radix Tree、Suffix Tree），以及使用场景和解决的问题。是不是感觉 hin 简单，都把握住了？

今天，我们继续围绕这个话题展开，再多介绍几种常见的树型结构。当然了，主要目的还是梳理它们使用的场景和解决的问题。

哈夫曼树(Huffman Tree)

哈夫曼树，又被称为最优二叉树，属于带权值二叉树的一种。它的真实节点全部分布在叶子节点中，是各种可能的组合中 WPL 值最小的形式。组合形式可能不唯一，但 WPL 值一定为最小。

介绍一下 WPL（Weighted Path Length），也就是 带权路径长度，说简单一些就是【节点到根节点的路径长度 * 该节点的权值】。说白了就是权值越大的节点，离根节点越近就对了。

WPL_A = 9x2+4x2+5x2+2x2 = 40WPL_B = 9x1+5x2+4x3+2x3 = 37WPL_C = 4x1+2x2+5x3+9x3 = 50

看一下上面这章图和三个对应的 WPL 的值，很明显可以看出来(b)是[9，4，5，2]这几个节点对应的哈夫曼树（的一种表现形式）。我们刚才也提了，哈夫曼树组成的形式可能不唯一，就比如说把(b)镜像过来看，也是哈夫曼树。

哈夫曼树的应用中，最有名的就是哈夫曼编码了。通过这种编码方式，可以使得整体编码的长度最短。还需要说明的是，它是一种前缀编码，任何一个编码值，都不会为其他编码值的前缀（最左子串）。

在 NLP(自然语言处理)领域划时代之作—— word2vec 的过程中，也通过哈夫曼树结构来加速查询高频词语，有兴趣的朋友可以了解一下。

最小生成树(Minimum Spanning Tree)

最小生成树，虽然叫做“树”，但是它更多的出现在“图”相关的知识中，描述的是将一个有权图，转化成 所有节点均可连通，并且连接边的权值之和最小的树形结构。

提到这个，就肯定要说一下大名鼎鼎的 Prim 算法 和 Kruskal 算法，这两种算法分别从 随机顶点的角度 和 权值最小的边的角度 出发，一步一步的选出适合的边，然后最终形成一颗包含全部 n 个节点和 n-1 条边的最小生成树。

这方面比较经典的应用，就比如多个城市之间建铁路，要求每个城市都连通、并且铁路距离总和最小这种问题。后来我想想，送外卖的时候兴许也能用到这个方法，该为 35 岁之后的职业生涯提前规划起来了。

线段树(Segment Tree)

线段树，是一种特殊的平衡二叉查找树，每个叶子节点表示一个真实的节点信息。而路径上所有的非叶子节点，用来表示它包含的各层级子节点的范围，并用于标记这个范围内的一些信息，比如范围内的 max 值或 sum 值等。

线段树可以较好的兼顾区间插入新数据和单点数据修改的逻辑。当更新叶子节点内容的时候，只要更新该节点对应路径上的节点信息即可。主要用于一些对范围查询有很高要求的场景。

值得一提的是，线段树可以通过一个一维数组来表示，如上图中绿色数字所示（其中 10、11 为空缺信息）。还需要说明的一点是，类似的概念还有区间树，也有人将这两个概念画了等号，大家自行了解分辨。

伸展树(Splay Tree)

伸展树是一颗非平衡二叉搜索树。它的设计思路是基于一种假设：最频繁被查询的信息，它（和它附近的节点）在下次查询的时候更可能被查到。所以，通过 Splay Tree 查询的时候，会随着被查询的信息，反复调整树本身的结构，从而将经常被查询到的节点，放到 root 附近。这样就可能会加速查询效率。

这个乍一听，有点像 LRU 或者 LFU 类似的结构，但又有所不同。首先，Splay Tree 中会保留所有的节点信息，不存在过期（或超限）销毁的情况。还有一点就是它并不是被查到之后立即置顶，会有一些其他的综合考量（比如，每次最多进行 n 次旋转）。

看一下上面这张图吧，它模拟的是（频繁）查询 R 的时候，Splay Tree 的变化情况。说白了就是把 R 节点放到根节点的位置，下次查起来就方便多了。

Splay Tree 比较适合做缓存，特别在热点数据相对集中的情况下，查询效率很高。举个应用的例子吧：我们常用的输入法，当你输入完拼音之后，会根据你的之前选择情况，优先出现某些词语。但很多情况下，又不会直接把你上次选择的词语直接置顶，这就可以理解为是参考了伸展树的思路（当今输入法的排序，实际更多的应该是用 AI 算法做概率预测，而非单纯的 Splay Tree）。

数据库领域

数据库中非常核心的一个部分，就是索引结构的设计——这几乎决定了数据库的应用领域。而索引结构的设计，又是数据结构和算法的“重灾区”。下面我们几种来列举几种数据库领域中，常见的树结构。

B 树

传统的二叉树中，每个节点中包含一个信息，这样如果节点数比较多，路径就会很深。路径深了，对应的问题就是查询的过程中，需要经过更多的节点，从而造成性能下降。基于此，B 树诞生了。

B 树也属于一种自平衡树。内部通过分裂机制，能够保持数据的有序。它的单个节点中可以保存 2~4 个信息。单个节点内部有序，节点之间信息的间隔，可以作为划分下面部分的依据。

看上面这张图，树中一共有 10 个信息，按照红黑树的形式存储，最长的路径应该是 4。而通过 B 树进行存储，就会显得“矮胖”了，对应的跨节点查询次数也就缩短了。

B 树比较适合于单点查询的场景，比较常见的应用就是 MongoDB 了。当然了，B 树也有一些不适合的场景，比如所有节点都放在磁盘上，则读写性能相对差；再比如说，如果我想查 5~9 范围内的所有数据，用 B 树是不是就需要在 3 个节点中反复横跳？

B+树

B+树就是为了解决上面抛出的两个问题而设计的。与 B 树相同的是，B+树的节点中也包含了多个信息。但相比于 B 树，B+树做了一些改动：非叶子节点中仅保留数据之间的相对关系，而所有的真实信息均包含在叶子节点中。这样的话，相对关系信息就可以放到内存中，而将所有节点信息（可以认为量较大）保留在磁盘中。

每次查询，通过相对关系，在内存中就可以快速的定位到具体的节点信息，从而减少磁盘的 IO 次数。这样做还有一个好处，可以通过一条“线”将所有叶子节点串联起来，从而方便做范围查询。大名鼎鼎的 Mysql 的存储引擎 InnoDB，使用的就是这种思路。

不知道有没有朋友跟我一样，在很长的一段时间内，把数据库索引和 B+树画上了等号。其实不然，不同应用领域的数据库，有着不同的索引结构。B+树的信息存放在磁盘中，且属于非顺序写入，所以查询性能很高，但写入的性能偏低。在大数据存储和日志服务等需要频繁写入操作的领域，就有些不合适了——这就要引出我们接下来的话题了。

日志结构化合并树（Log Structured Merge Tree）

多年前，谷歌在发大据领域发表了Big Table相关论文，LSM 树是其中的实现思路。我第一次听说 LSM Tree，是有幸跟一位 HBase 领域的资深大佬一起喝茶的时候。当时我红着脸表示，只听说过其中的一部分。

与其说它是一种数据结构，其实它更像是基于此思想而衍生出的一系列算法操作的集合。它描述了将实时产生的大批量信息在内存中排序、更新，然后按批次顺序写入磁盘固化、合并的流程，从而兼顾了大批量数据的高效写入存储和范围查询等使用场景。

我们刚才提到，B+树结构的存储索引并不适合在频繁写入的场景，其中一个很重要的原因就是因为它属于非顺序写入。而针对传统磁盘来说，由于扇区物理结构轮转，顺序写入的性能远好于非顺序写入。

•随机写入磁盘慢了咋办？

将非顺序的信息在内存中攒成有序的一批信息（Segment），然后一次性写入磁盘不就好了么。

•攒批的时候，数据丢失或者进程崩溃了咋办？

提前把数据写到一个本地日志文件（WAL 机制）里做备胎（不对，是备份）不就好了。

•需要在批量数据中做范围查找了咋办？

在内存中记录每个 Segment（默认有序）的起止范围，每次查询的时候仅查询范围内的 Segment 不就好了。

•数据量太大，磁盘中的 Segment 太多，影响查询性能了咋办？

当每个 Segment 大到一定的程度的时候，把几个 Segment 做归并排序，然后合并到一个大的 Segment 里不就好了么。

•写入数据之后，想删除咋办？

根据 key 找到最后一次写入的信息，打上墓碑记号。查询到的时候，返回“这个真没有”不就好了么。

•墓碑记号太多，占用大量内存，咋办？•单点信息查询，数据太多，而且经常 miss，咋办？•范围查询，不好确认从哪个 Segment 开始，咋办？•...

随着大数据的爆火，LSM Tree 被广泛用于 KV 型数据库和 OLAP 场景中，比如纯序员熟悉（拼写方式）的 HBase、Cassandra、LevelDB 等。相关领域的实际问题太多了，同样的，解法也很多。有兴趣的朋友可以深入了解一下。

本章小节

本章中，我们又介绍了几种常见的树形结构和相关使用场景。旨在说明，Tree 在编码、缓存、数据库等领域也有着广泛的应用。特别需要强调的是，在数据库的存储引擎设计方面，Tree 可是占据了半壁江山，这其中还有没有用到其他类型的树？

那在类似人工智能这种图结构占据主导位置的领域，树结构是否有它的一技之长呢？还有什么行业，会涉及到树结构呢？我们在下一章中，会跟大家继续这个话题。

对这方面感兴趣的朋友，欢迎添加我的微信。彼此交流学习的经验和心得，我还有一些很可（dou）爱（bi）的微信表情想跟你分享哦。

推荐阅读

•心中有“树”！图文并茂介绍数据结构中常见的树（一）•记住这两个二分模板，秒杀所有二分查找算法题！•人生重开模拟器突然火爆 GitHub，赶紧来玩一玩

长按识别下图二维码，关注公众号「Doocs 开源社区」，第一时间跟你们分享好玩、实用的技术文章与业内最新资讯。