百度统计
一面之猿网
让这个世界,因为我,有一点点的不一样
纯序员给你介绍常用的数据结构——树(二)

大家好,我是不会写代码的纯序员——Chunel Feng。在上一章中,我们介绍了6种常见的树结构(BST,AVL,RB Tree,Trie Tree、Radix Tree、Suffix Tree),以及使用场景和解决的问题。是不是感觉hin简单,都把握的住?今天,我们接着聊这个话题,再多介绍几种树。

哈夫曼树(Huffman Tree)

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

image.png

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

WPL_A = 9x2+4x2+5x2+2x2 = 40

WPL_B = 9x1+5x2+4x3+2x3 = 37

WPL_C = 4x1+2x2+5x3+9x3 = 50

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

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

最小生成树(Minimum Spanning Tree)

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

提到这个,就肯定要说一下大名鼎鼎的 Prim算法Kruskal算法,这两种算法分别从 随机顶点的角度权值最小的边的角度 出发,一步一步的选出适合的边,然后最终形成一颗包含全部n个节点和n-1条边的最小生成树。对具体流程不了解的朋友,可以自己百度或者B站一下,相关的介绍有很多。

image.png

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

线段树(Segment Tree)

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

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

image.png

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

伸展树(Splay Tree)

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

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

image.png

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

Splay Tree比较适合做缓存,特别在热点数据相对集中的情况下,查询效率很高。举个应用的例子吧:我们常用的输入法,当你输入完拼音之后,会根据你的之前选择情况,优先出现某些词语。但很多情况下,又不会直接把你上次选择的词语直接置顶,这就可以理解为是参考了伸缩树的思路。

数据库领域

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

B树

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

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

image.png

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

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

B+树

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

image.png

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

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

日志结构化合并树(Log Structured Merge Tree)

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

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

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

image.png

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

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

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

提前把数据写到一个本地文件(WAL机制)里做备胎(不对,是备份)不就好了。

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

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

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

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

  • 写入数据之后,想删除咋办?

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

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

image.png

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

本章小节

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

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

还是那句话,对这方面感兴趣的朋友,欢迎填加我的微信。彼此交流学习的经验和心得,还可以互相说说段子哦。

image

    					[2021.11.20 by Chunel]

推荐阅读


个人信息

微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站:www.chunel.cn
github地址: https://github.com/ChunelFeng

image