高级数据结构

⼀一.数据结构的基本问题

数据在计算机系统中的表⽰示和组织，但是有约束内存结构：⼆二叉树-平衡-近似平衡-不平衡 优化 时间外存结构：B+树、R树、希尔伯特树 优化 I/O次数云存储结构：分布式散列表（巨⼤大规模）

Compact（紧缩）存储：哈夫曼编码、FP树（前缀、trie树）、Lossy-Counting（有损计数）

区间树、k-d 树、红⿊黑树、红⿊黑树的拓展（应⽤用）数据压缩

算法：搜索、排序、匹配（matching）

⼆二.基本思想基本⽅方法

A)空间换时间 跳表 树节点增加更多指针B)困难：

(1)访问的次线性 O(logn) 线性的困难在于扫描整个数据集(2)数据

a)规模 访问的规模 巨⼤大规模 b)动态性

c)复杂性（链值、结构化数据、⾮非结构化数据） d)安全性

(3)外存的访问模式（如何减⼩小 I/O 次数） (4)存储体系/平台/介质

a)内存：树（平衡树 近似平衡树 不平衡树） 访问 O(logn)

b)外存：B+树（⼀一维）、R 树（⼀一维到⼆二维）、Hilbert树（⼆二维到⼀一维） c)分布式：CAN 散列表、CHORD 链表、BATON B+树

C)具体⽅方法：希尔排序（初等数论、数逆序）、数学期望（和的期望等于期望的和）、分形

有哪些数据结构 应⽤用场景 解决什么问题 是怎么做的 背后原理 为什么这么做 如何改进 相互关系

哪些情况会让问题变得困难 如何解决对数据结构的整理分类⾃自⼰己的理解

关键技术的基本思想 简短清晰表达 重点突出 总分结构表达能⼒力是评价的因素

例题：

1.写出BST/红⿊黑树/B+/Spaly树之间的区别和应⽤用场景2.⼀一致哈希表在分布式⺴⽹网络中的应⽤用和性能优化

分布式哈希(DHT)

两个关键点：每个节点只维护⼀一部分路由；每个节点只存储⼀一部分数据。从⽽而实现整个⺴⽹网络中的寻址和存储。⼀一致性哈希：

DHT的⼀一种实现。本质还是⼀一个哈希算法。

四个概念和原则：

a)balance：哈希结果尽可能的平均分散到各个节点上，使得每个节点都能得到充分利⽤用。b)Monotonicity：上⾯面也说了，如果是⽤用签名取模算法，节点变更会使得整个⺴⽹网络的映射关系更改。如果是carp，会使得1/n的映射关系更改。⼀一致性哈希的⺫⽬目标，是节点变更，不会改变⺴⽹网络的映射关系。

c)spread：同⼀一份数据，存储到不同的节点上，换⾔言之就是系统冗余。⼀一致性哈希致⼒力于降低系统冗度。

d)load：负载分散，和balance其实是差不多的意思，不过这⾥里更多是指数据存储的均衡，balance是指访的均衡。

⼀一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的⺴⽹网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息，并且在节点加⼊入/退出系统时，仅有相关的少量节点参与到拓扑的维护中。所有这⼀一切使得⼀一致性哈希成为第⼀一个实⽤用的DHT算法。

但是⼀一致性哈希的路由算法尚有不⾜足之处。在查询过程中，查询消息要经过O(N)步(O(N)表⽰示与N成正⽐比关系，N代表系统内的节点总数)才能到达被查询的节点。不难想象，当系统规模⾮非常⼤大时，节点数量可能超过百万，这样的查询效率显然难以满⾜足使⽤用的需要。换个⾓角度来看，即使⽤用户能够忍受漫⻓长的时延，查询过程中产⽣生的⼤大量消息也会给⺴⽹网络带来不必要的负荷。

3.内存/外存对于数据结构选择的影响？

内存指的就是主板上的存储部件，CPU直接与之沟通，并⽤用其存储数据的部件，存放当前正在使⽤用的（即执⾏行中的）数据和程序，它的物理实质就是⼀一组或多组具备数据输⼊入输出和数据存储功能的集成电路，内存只⽤用于暂时存放程序和数据，⼀一旦关闭电源或发⽣生断电，其中的程序和数据就会丢失。外存包括软盘、硬盘和光盘，存放在其中的数据靠磁来维持，因此可永久保存数据。

特点：内存处理速度快、存储容量⼩小、断电后信息丢失；外存处理速度慢、存储容量⼤大、信息永久保存

4.R树在地图/打⻋车软件中的应⽤用和性能分析

数据结构

本质：Data Structure == ( Data Set, Pointer ) == (存储结构，指针)

定义：A particular way to organize data in the operation system to accessdata efficiently.

内容：(1)数据的各种逻辑结构和物理结构，以及他们之间的相应关系 (2)并对每种结构定义相适应的各种运算 (3)设计出相应的算法 分析算法的效率逻辑结构：线性（栈、队列） ⾮非线性（树、图）数据的存储结构：线性连续的存储单元数据操作的集合：查询、更新和聚集

什么是好的数据结构：(1) O(logn)时空复杂度 (2)合理的内存开销 (3)正确性 (4)易编程、易读

⾼高级数据结构

对于数据密集型（⼤大数据）的应⽤用，能够设计出⼀一种数据结构，让我们的算法有很好的响应性

算法

定义：解题⽅方⽽而完整的描述，是⼀一系列解决问题的清晰指令，对⼀一系列规范的输⼊入，在有序的时间内获得所要求的输出；有基本运算及规定的运算顺序所构成的完整的解题步骤。按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决⼀一类问题。

内容：排序、分治法（divide and conquer）、随机算法、数据结构的算法、动态规划、贪⼼心算法、图算法、数论算法

三.具体数据结构及关系Skiplist 跳表

1.为什么选择跳表？

跳表是⼀一种随机化的数据结构，它的效率和红⿊黑树以及 AVL 树不相上下，跳表的原理相当简单，只要能熟练操作链表，就能轻松实现⼀一个 SkipList。

有序数组，如果数据量不断变化，有序数组很难能够⾼高效的进⾏行写⼊入。

链表是⼀一种最容易处理数据不断增加结构的有序数据结构，并且链表对于并发的⽀支持度是⾮非常好的，然⽽而链表却不能够进⾏行⼆二分查找，因为⽆无法取到任意⼦子集的中值。

树，如平衡有序⼆二叉树。不过，⽆无论是AVL还是红⿊黑树，这个预先找到中值并写⼊入到⽗父节点的操作的都是⾮非常复杂的，对于复杂的操作来说，想使⽤用常⻅见的⽆无锁操作就⼏几乎不可能了。所以，跳表是⼀一种满⾜足这样条件的很好的数据结构。

2.定义：

是⼀一种随机化数据结构，基于并联的链表，其效率可⽐比拟于⼆二叉查找树（对于⼤大多数操作需要O(log n)平均时间）

跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的⽅方式进⾏行的，所以在列表中的查找可以快速的跳过部分列表。所有操作都以对数随机化的时间进⾏行O(logn)。

3.描述：

跳跃列表是按层建造的。底层是⼀一个普通的有序链表。每个更⾼高层都充当下⾯面列表的“快速跑道”，这⾥里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起来，每个元素都在 1/(1-p) 个列表中出现，⽽而最⾼高层的元素（通常是在跳跃列表前端的⼀一个特殊的头元素）在 O(log1/p n) 个列表中出现。

每个节点包含2个指针。⼀一个指向同⼀一层中下⼀一元素，另⼀一个指向下⼀一层元素。

要查找⼀一个⺫⽬目标元素，起步于头元素和顶层列表，并沿着每个链表搜索，直到到达⼩小于或着等于⺫⽬目标的最后⼀一个元素。通过跟踪起⾃自⺫⽬目标直到到达在更⾼高列表中出现的元素的反向查找路径，在每个链表中预期的步数显⽽而易⻅见是 1/p。所以查找的总体代价是 O((log1/p n) / p)，当p 是常数时是 O(log n)。通过选择不同 p 值，就可以在查找代价和存储代价之间作出权衡。

插⼊入时被插⼊入元素的层数也是随机化得到。

跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证，因为⽤用来建造跳跃列表的扔硬币⽅方法(随机的)总有可能（尽管概率很⼩小）⽣生成⼀一个糟糕的不平衡结构。但是在实际中它⼯工作的很好，随机化平衡⽅方案⽐比在平衡⼆二叉查找树中⽤用的确定性平衡⽅方案容易实现。跳跃列表在并⾏行计算中也很有⽤用，这⾥里的插⼊入可以在跳跃列表不同的部分并⾏行的进⾏行，⽽而不⽤用全局的数据结构重新平衡。

4.核⼼心思想：空间换取时间，在每个节点中增加向前的指针，提⾼高查找的效率5.优点：

a)⽀支持范围查找

因为是有序结构，所以能够很好的⽀支持范围查找。截取中间⼦子集只需两次定位。耗时

2*log2n

b)能够随着数据的增⻓长⽽而⾃自动扩展。核⼼心数据结构是链表，可以很好的⽀支持数据的不断增⻓长 c)读写性好

因为从宏观上可以做到⼀一次排除⼀一半的数据，并且在写⼊入时也没有进⾏行其他额外的数据查找

性 ⼯工作，所以对于skiplist来说，其读写的时间复杂度都是O(log2n) d)并⾏行度⾼高

只要不是在同⼀一个⺫⽬目标插⼊入点插⼊入数据，所有插⼊入都可以并⾏行进⾏行，⽽而就算在同⼀一个插⼊入

点，插⼊入本⾝身也可以使⽤用⽆无锁⾃自旋来提升写⼊入效率。因此skiplist是个并⾏行度⾮非常⾼高的数据结构。

e)内存占⽤用：因为每个结点期望是2层，所以储存占⽤用空间⼤大概为2N，与平衡⼆二叉树的内存

消耗基本⼀一致。 6.改进

a)若不采⽤用随机产⽣生层数⽅方法还可采⽤用⼆二分的⽅方法建⽴立初始SkipList，估计复杂度仍然

是O(log n)，系数会更⼩小。

b)进⾏行随机数的运算本⾝身也是个很消耗cpu的操作，所以，如果在插⼊入的时候就能直接算出这个数据应该往⾼高层推的总次数，那么就不需要算那么多次随机数了，每次写⼊入只需要算⼀一次就⾏行了。

c)实现⼀一个⾼高性能的随机数算法。

树的分类：

(1)BST：⼆二叉查找/搜索/排序树(2)AVL 树：平衡⼆二叉查找树

(3)红⿊黑树：基本平衡⼆二叉查查找树(4)Splay 树：伸展树/树(5)B 树：多路平衡查查找树(6)B+树(7)R 树

最基本：BST ⼆二叉搜索树 不平衡

定义：⼆二叉排序树或者是⼀一棵空树，或者是具有下列性质的⼆二叉树：（1）若左⼦子树不空，则左⼦子树上所有结点的值均⼩小于它的根结点的值；

（2）若右⼦子树不空，则右⼦子树上所有结点的值均⼤大于或等于它的根结点的值；（3）左、右⼦子树也分别为⼆二叉排序树；（4）没有键值相等的节点。

操作：查询（时间复杂度 O(logn)）、插⼊入、删除

应⽤用：⽀支持多种动态集合操作、表⽰示有序集合、建⽴立索引或优先队列

缺点：作⽤用于⼆二叉查找树上的基本操作的时间是与树的⾼高度成正⽐比的。对⼀一个含n各节点的

完全⼆二叉树，这些操作的最坏情况运⾏行时间为O(log n)。但如果树是含n个节点的线性链，则这些操作的最坏情况运⾏行时间为O(n)。⽽而有些⼆二叉查找树的变形，其基本操作在最坏情况下性能依然很好，⽐比如红⿊黑树、AVL树等等。

BST 的改进：Splay Tree 拓展树 不平衡

1.什么是 Splay Tree?

核⼼心思想：通过 Splay操作进⾏行⾃自我调整，获得平摊较低的时间复杂度

⼀一种⼆二叉查找树，它能在O(log n)内完成插⼊入、查找和删除操作。

在伸展树上的⼀一般操作都基于伸展操作：假设想要对⼀一个⼆二叉查找树执⾏行⼀一系列的查找操作，为了使整个查找时间更⼩小，被查频率⾼高的那些条⺫⽬目就应当经常处于靠近树根的位置。于是想到设计⼀一个简单⽅方法， 在每次查找之后对树进⾏行重构，把被查找的条⺫⽬目搬移到离树根近⼀一些的地⽅方。伸展树应运⽽而⽣生。伸展树是⼀一种⾃自调整形式的⼆二叉查找树，它会沿着从某个节点到树根之间的路径，通过⼀一系列的旋转把这个节点搬移到树根去。它的优势在于不需要记录⽤用于平衡树的冗余信息。

2.与 BST 的关系

是对⼆二叉查找树的⼀一种改进，虽然它并不能保证树⼀一直是“平衡”的，但对于伸展树的⼀一系列操作，我们可以证明其每⼀一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是⼀一种平衡的⼆二叉查找树。⽽而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。和 BST ⼀一样，是有序的（左⼩小右⼤大）。

3.优点：

可靠的性能——它的平均效率不输于其他平衡树

存储所需的内存少——伸展树⽆无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占⽤用要⼩小。

⽀支持可持久化——可以将其改造成可持久化伸展树。可持久化数据结构允许查询修改之前数据结构的信息，对于⼀一般的数据结构，每次操作都有可能移除⼀一些信息，⽽而可持久化的数据结构允许在任何时间查询到之前某个版本的信息。可持久化这⼀一特性在函数式编程当中⾮非常有⽤用。另外，可持久化伸展树每次⼀一般操作的均摊复杂度是O(log n)

4.缺点：

伸展树最显著的缺点是它有可能会变成⼀一条链。这种情况可能发⽣生在以⾮非降顺序访问n个元素之后。然⽽而均摊的最坏情况是对数级的——O(log n)

BST 的改进：RB Tree 红⿊黑树 近似平衡

1.什么是红⿊黑树？

红⿊黑树是⼀一种⾃自平衡⼆二叉查找树，典型的⽤用途是实现关联数组。它是复杂的，但它的操作有着良好的最坏情况运⾏行时间，并且在实践中是⾼高效的: 它可以在O(log n)时间内做查找，插⼊入和删除，这⾥里的n是树中元素的数⺫⽬目。

如何保持平衡？通过对任何⼀一条从根到叶⼦子的简单路径上的各个结点的性质进⾏行约束，确保没有⼀一条路径会⽐比其他路径⻓长出两倍，因⽽而近似于平衡。红⿊黑树不追求完全平衡，降低了对选择的要求，从⽽而提⾼高了性能。

结点属性：树中每个结点包含5个属性：color, key, left, right 和 p 。视叶结点（外部结点）属性值为NIL，⽽而把带关键字的结点视为树的内部结点。

⿊黑⾼高（black height）：从这棵红⿊黑树的根结点（但不包括这个根结点）到叶结点的任意⼀一条简单路径上包含的⿊黑⾊色结点个数（注意，包括叶结点），记为bh(x)。另外规定叶结点的⿊黑⾼高度为0。

树的旋转：当我们在对红⿊黑树进⾏行插⼊入和删除等操作时，对树做了修改，那么可能会违背红⿊黑树的性质。为了保持红⿊黑树的性质，我们可以通过对树进⾏行旋转，即修改树种某些结点的颜⾊色及指针结构，以达到对红⿊黑树进⾏行插⼊入、删除结点等操作时，红⿊黑树依然能保持它特有的性质。

2.⽤用途和好处

红⿊黑树和AVL树⼀一样都对插⼊入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应⽤用如实时应⽤用（real time application）中有价值，⽽而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算⼏几何中使⽤用的很多数据结构都可以基于红⿊黑树。红⿊黑树和 AVL 树时间复杂度相同，但红⿊黑树统计性能更好。

红⿊黑树在函数式编程中也特别有⽤用，在这⾥里它们是最常⽤用的持久数据结构（persistentdata structure）之⼀一，它们⽤用来构造关联数组和集合，每次插⼊入、删除之后它们能保持为以前的版本。除了O(log n)的时间之外，红⿊黑树的持久版本对每次插⼊入或删除需要O(log n)的空间。

3.性质：

红⿊黑树是每个节点都带有颜⾊色属性的⼆二叉查找树，颜⾊色为红⾊色或⿊黑⾊色。性质1. 节点是红⾊色或⿊黑⾊色。性质2. 根是⿊黑⾊色。

性质3. 所有叶⼦子都是⿊黑⾊色（叶⼦子是NIL节点）。

性质4. 每个红⾊色节点必须有两个⿊黑⾊色的⼦子节点。(从每个叶⼦子到根的所有路径上不能有两个连续的红⾊色节点。)

性质5. 从任⼀一节点到其每个叶⼦子的所有简单路径都包含相同数⺫⽬目的⿊黑⾊色节点。

B Tree / B+ Tree 平衡多叉树1.为什么需要 B 树？

动态查找树主要有：⼆二叉查找树，平衡⼆二叉查找树，红⿊黑树，B-tree/B+-tree。前三者是典型的⼆二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度⾃自然会提⾼高查找效率。

但是咱们⾯面对这样⼀一个实际问题：就是⼤大规模数据存储中，实现索引查询这样⼀一个实际背景下，树节点存储的元素数量是有限的（如果元素数量⾮非常多的话，查找就退化成节点内部的线性查找了），这样导致⼆二叉查找树结构由于树的深度过⼤大⽽而造成磁盘I/O读写过于频繁，进⽽而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），⼀一个基本的想法就是：采⽤用多叉树结构（由于树节点元素数量是有限的，⾃自然该节点的⼦子树数量也就是有限的）。这样我们就提出了⼀一个新的查找树结构——多路查找树。根据平衡⼆二叉树的启发，⾃自然就想到平衡多路查找树结构，也就是这篇⽂文章所要阐述的第⼀一个主题B~tree，B树的各种操作能使B树保持较低的⾼高度，从⽽而达到有效避免磁盘过于频繁的查找存取操作，从⽽而有效提⾼高查找效率。

磁盘读取数据是以盘块(block)为基本单位的。位于同⼀一盘块中的所有数据都能被⼀一次性全部读取出来。⽽而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同⼀一盘块，同⼀一磁道中。或者⾄至少放在同⼀一柱⾯面或相邻柱⾯面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts。

所以，在⼤大规模数据存储⽅方⾯面，⼤大量数据存储在外存磁盘中，⽽而在外存磁盘中读取/写⼊入块(block)中某数据时，⾸首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要⼀一种合理⾼高效的外存数据结构，即B-tree结构，以及相关的变种结构：B+-tree结构。2.B 树与红⿊黑树的关系

B树与红⿊黑树最⼤大的不同在于，B树的结点可以有许多⼦子⼥女，从⼏几个到⼏几千个。那为什么⼜又说B树与红⿊黑树很相似呢?因为与红⿊黑树⼀一样，⼀一棵含n个结点的B树的⾼高度也为O（lgn），但可能⽐比⼀一棵红⿊黑树的⾼高度⼩小许多，应为它的分⽀支因⼦子⽐比较⼤大。所以，B树可以在O（logn）时间内，实现各种如插⼊入（insert），删除（delete）等动态集合操作。3.B 树与 B+树的关系

⼆二叉树提供了良好的性能，但是当数据有序插⼊入时会失去平衡，2-3-4树和2-3树是⼀一种平衡树,是多路的，⽽而红-⿊黑树是⼀一种⼆二叉平衡树，通过严格的红⿊黑规则保持平衡。B树是⼀一种平

衡的多路查找树，可以看做⼀一种扩展的2-3-4树，它的数据项个数和⼦子节点数没有(如果结点的元素数量⾮非常多的话那就退化成节点内部的线性查找了)，在⽂文件系统中有所应⽤用，主要⽤用作⽂文件的索引。

B树插⼊入节点要注意从⼦子节点开始,⼀一直上溯到根

B+-tree：是应⽂文件系统所需⽽而产⽣生的⼀一种B-tree的变形树。

⼀一棵m阶的B+树和m阶的B树的差异在于：

1.有n棵⼦子树的结点中含有n个关键字； (⽽而B 树是n棵⼦子树有n-1个关键字)

2.所有的叶⼦子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶⼦子结点本⾝身依关键字的⼤大⼩小⾃自⼩小⽽而⼤大的顺序链接。 (⽽而B 树的叶⼦子节点并没有包括全部需要查找的信息)

3.所有的⾮非终端结点可以看成是索引部分，结点中仅含有其⼦子树根结点中最⼤大（或最⼩小）关键字。 (⽽而B 树的⾮非终节点也包含需要查找的有效信息)

B+树中的⾮非叶⼦子节点不是最终指向⽂文件内容的节点，⽽而只是叶⼦子节点中关键字的索引。所有的叶⼦子节点包含了全部关键字的信息，且叶⼦子节点本⾝身依关键字⾃自⼩小⽽而⼤大顺序链接。所以任何关键字的查找都必须⾛走⼀一条从根节点到叶⼦子节点的路(导致每⼀一个数据的查询效率相当)。

为什么说B+-tree⽐比B 树更适合实际应⽤用中操作系统的⽂文件索引和数据库索引？a) B+-tree的磁盘读写代价更低

B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更⼩小。如果把所有同⼀一内部结点的关键字存放在同⼀一盘块中，那么盘块所能容纳的关键字数量也越多。⼀一次性读⼊入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。举个例⼦子，假设磁盘中的⼀一个盘块容纳16bytes，⽽而⼀一个关键字2bytes，⼀一个关键字具体信息指针2bytes。⼀一棵9阶B-tree(⼀一个结点最多8个关键字)的内部结点需要2个盘快。⽽而B+ 树内部结点只需要1个盘快。当需要把内部结点读⼊入内存中的时候，B 树就⽐比B+ 树多⼀一次盘块查找时间(在磁盘中就是盘⽚片旋转的时间)。b) B+-tree的查询效率更加稳定

由于⾮非终结点并不是最终指向⽂文件内容的结点，⽽而只是叶⼦子结点中关键字的索引。所以任何关键字的查找必须⾛走⼀一条从根结点到叶⼦子结点的路。所有关键字查询的路径⻓长度相同，导致每⼀一个数据的查询效率相当。

c) B+-tree的应⽤用: VSAM(虚拟存储存取法)⽂文件

总⽽而⾔言之，B 树在提⾼高了磁盘IO 性能的同时并没有解决元素遍历效率低下的问题。正是为了解决这个问题，B+树应运⽽而⽣生。B+树只要遍历叶⼦子节点就可以实现整棵树的遍历，⽀支持基于范围的查询，⽽而B树不⽀支持range-query 这样的操作（或者说效率太低）。

R Tree 平衡树

1.R-Tree是什么，它要解决什么问题？

⺫⽬目前应⽤用最为⼲⼴广泛的⼀一种空间索引结构。R树是⼀一个⾼高度平衡树，它是B树在k维上的⾃自然扩展，⽤用空间对象的MBR来近似表达空间对象，根据地物的MBR建⽴立R树，可以直接对空间中占据⼀一定范围的空间对象进⾏行索引。R树的每⼀一个结点都对应着磁盘⻚页D和区域I，如果结点不是叶结点，则该结点的所有⼦子结点的区域都在区域I的范围之内，⽽而且存储在磁盘⻚页D中。如果结点是叶结点，那么磁盘⻚页D中存储的将是区域I范围内的⼀一系列⼦子区域，⼦子区域紧紧围绕空间对象，⼀一般为空间对象的外接矩形。

R树运⽤用了空间分割的理念，这种理念是如何实现的呢？R树采⽤用了⼀一种称为MBR(Minimal Bounding Rectangle)的⽅方法，在此我把它译作“最⼩小边界矩形”。从叶⼦子结点开始⽤用矩形（rectangle）将空间框起来，结点越往上，框住的空间就越⼤大，以此对空间进⾏行分割。

在⼤大规模数据存储中，⼆二叉查找树结构由于树的深度过⼤大⽽而造成磁盘I/O读写过于频繁，

进⽽而导致查询效率低下，为了减少I/O次数，诞⽣生了B-Tree。⽽而R树是B树在⾼高维空间的扩展。R树将⾼高纬空间逐步划分，⼤大的空间⾥里都包含若干个⼩小的空间，每⼀一个空间相当于树的节点，由此构成⼀一个类似于B-Tree的树，只是它的节点存储的是⾼高维的空间信息。这种结构使我们不必遍历空间中的所有位置即可找到想要的位置。

举例：如何查询特定的数据吧。⼜又以餐厅为例吧。假设我要查询⼲⼴广州市天河区天河城附近⼀一公⾥里的所有餐厅地址怎么办？打开地图（也就是整个R树），先选择国内还是国外（也就是根结点）。然后选择华南地区（对应第⼀一层结点），选择⼲⼴广州市（对应第⼆二层结点），再选择天河区（对应第三层结点），最后选择天河城所在的那个区域（对应叶⼦子结点，存放有最⼩小矩形），遍历所有在此区域内的结点，看是否满⾜足我们的要求即可。

2.缺点及改进：

a)最佳应⽤用范围是处理2⾄至6维的数据，更⾼高维的存储会变得⾮非常复杂。

b)存储空间信息需要较⼤大的存储空间，改进结构为Hilbert R-Tree。

c)R树兄弟结点对应的空间区域可以重叠，可以较容易地进⾏行插⼊入和删除操作。但正因为区域之间有重叠，空间索引可能要对多条路径进⾏行搜索后才能得到最后的结果。当查找与给定的查询窗⼝口相交的所有空间对象时，空间搜索算法是从根结点开始，向下搜索相应的⼦子树．算法递归遍历所有约束矩形与查询窗⼝口相交的⼦子树，当到达叶结点时，边界矩形中的元素被取出并测试其是否与查询矩形相交，所有与查询窗⼝口相交的叶结点即为要查找的空间对象。R树的查询效率会因重叠区域的增⼤大⽽而⼤大⼤大减弱，在最坏情况下，其时间复杂度甚⾄至会由对数搜索退化成线性搜索。3.R树与 B 树的关系

R树是B树在空间的扩展，是⼀一种平衡的树结构。R树结构采⽤用平⾏行于数据空间轴的最⼩小的边界矩形来近似复杂的空间对象，其主要优点是⽤用⼀一定数量的字节来表⽰示⼀一个复杂的对象。尽管这样会丢失很多的信息，但是空间物体的最⼩小边界矩形保留了物体的最重要的⼏几何特性，即空间物体的位置和其在整个坐标轴上的范围。

Hilbert R Tree

R 树的变种，将⼆二维转化成⼀一维，简化问题。应⽤用于空间搜索。

an R-tree variant, is an index for multidimensional objects like lines, regions, 3-D

objects, or high-dimensional feature-based parametric objects. It can be thought of as anextension to B+-tree for multidimensional objects.

The performance of R-trees depends on the quality of the algorithm that clusters thedata rectangles on a node. Hilbert R-trees use space-filling curves, and specificallythe Hilbert curve, to impose a linear ordering on the data rectangles.

There are two types of Hilbert R-trees, one for static databases, and one for

dynamic databases. In both cases Hilbert space-filling curves are used to achieve betterordering of multidimensional objects in the node. This ordering has to be ‘good’, in thesense that it should group ‘similar’ data rectangles together, to minimize the area andperimeter of the resulting minimum bounding rectangles (MBRs). Packed Hilbert R-treesare suitable for static databases in which updates are very rare or in which there are noupdates at all.

K-d Tree

1.什么是 k-d树？

是⼀一种分割k维数据空间的数据结构。主要应⽤用于空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D树是⼆二进制空间分割树的特殊的情况。k-d 树的建⽴立就是空间的过程。时间复杂度为 O(logn)

2.应⽤用背景

特征点匹配实际上就是⼀一个通过距离函数在⾼高维⽮矢量之间进⾏行相似性检索的问题。针对如何快速⽽而准确地找到查询点的近邻，现在提出了很多⾼高维空间索引结构和近似查询的算法，k-d树就是其中⼀一种。

索引结构中相似性查询有两种基本的⽅方式：⼀一种是范围查询（range searches），另⼀一种是K近邻查询（K-neighbor searches）。范围查询就是给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离⼩小于阈值的数据；K近邻查询是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，就是最近邻查询（nearest neighborsearches）。

特征匹配算⼦子⼤大致可以分为两类。⼀一类是线性扫描法，即将数据集中的点与查询点逐⼀一进⾏行距离⽐比较，也就是穷举，缺点很明显，就是没有利⽤用数据集本⾝身蕴含的任何结构信息，搜索效率较低，第⼆二类是建⽴立数据索引，然后再进⾏行快速匹配。因为实际数据⼀一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以⼤大⼤大加快检索的速度。索引树属于第⼆二类，其基本思想就是对搜索空间进⾏行层次划分。根据划分的空间是否有混叠可以分为

Clipping和Overlapping两种。前者划分空间没有重叠，其代表就是k-d树；后者划分空间相互有交叠，其代表为R树。

3.与 BST 的区别：

k-d树的查找算法的回溯的，回溯检查总是从优先级最⾼高的树节点开始，优先队列与搜索路径同时⽣生成。4.缺点：

许多不必要的回溯和⽐比较的节点。训练实例远⼤大于空间维数。

FP Tree 频繁模式树

1.什么是 FP 树？

(1)频繁模式树(Frequent Pattern tree)简称为FP-tree，是满⾜足下列条件的⼀一个树结构：它由⼀一个根节点(值为null)、项前缀⼦子树(作为⼦子⼥女)和⼀一个频繁项头表组成。

(2)项前缀⼦子树中的每个结点包括三个域：item_name、count和node_link，其中：

item_name记录结点表⽰示的项的标识；count记录到达该结点的⼦子路径的事务数；node_link⽤用于连接树中相同标识的下⼀一个结点，如果不存在相同标识下⼀一个结点，则值为“null”。

(3)频繁项头表的表项包括⼀一个频繁项标识域：item_name和⼀一个指向树中具有该项标识的第⼀一个频繁项结点的头指针：head of node_link。

对于包含在FP-tree中某个结点上的项α，将会有⼀一个从根结点到达α的路径，该路径中不包含α所在结点的部分路径称为α的前缀⼦子路径(prefix subpath)，α称为该路径的后缀。在⼀一个FP-tree中，有可能有多个包含α的结点存在，它们从频繁项头表中的α项出发，通过项头表中的head of node_link和项前缀⼦子树中的node_link连接在⼀一起。FP-tree中每个包含α的结点可以形成α的⼀一个不同的前缀⼦子路径，所有的这些路径组成α的条件模式基(conditionalpattern base)。⽤用α的条件模式基所构建的FP-tree称为α的条件模式树(conditional FP-tree)。

2.构造算法

Apriori算法是⼀一种最有影响的挖掘布尔关联规则频繁项集的算法。是基于这样的事实：算

法使⽤用频繁项集性质的先验知识。Apriori使⽤用⼀一种称作逐层搜索的迭代⽅方法，k-项集⽤用于探索(k+1)-项集。⾸首先，找出频繁1-项集的集合。该集合记作L1。L1⽤用于找频繁2-项集的集合L2，⽽而L2⽤用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要⼀一次数据库扫描。  这个算法的思路，简单的说就是如果集合I不是频繁项集，那么所有包含集合I的更⼤大的集合也不可能是频繁项集。Apriori 的时空复杂度在海量数据下都不能忽略。

FP Tree 算法：在不⽣生成候选项的情况下，完成Apriori算法的功能

输⼊入：事务数据库D和最⼩小⽀支持度阈值minσ。输出：D所对应的FP-tree。

⽅方法：FP-growth算法(Frequent Pattern-growth)使⽤用了⼀一种紧缩的数据结构来存储查找频繁项集所需要的全部信息。

(1)扫描事务库D，获得D中所包含的全部频繁项集1F，及它们各⾃自的⽀支持度。对1F中的频繁项按其⽀支持度降序排序得到L。

(2)创建FP-tree的根结点T，以“null”标记。再次扫描事务库。对于D中每个事务，将其中的频繁项选出并按L中的次序排序。设排序后的频繁项表为[p|P]，其中p是第⼀一个频繁项，⽽而P是剩余的频繁项。调⽤用insert_tree([p|P],T)。insert_tree([p|P],T)过程执⾏行情况如下：如果T有⼦子⼥女N使N .item_name=p.item_name，则N的计数增加1；否则创建⼀一个新结点N，将其计数设置为1，链接到它的⽗父结点T，并且通过node_link将其链接到具有相同item_name的结点。如果P⾮非空，递归地调⽤用insert_tree(P，N)。FP-tree是⼀一个⾼高度压缩的结构，它存储了⽤用于挖掘频繁项集的全部信息。FP-tree所占⽤用的内存空间与树的深度和宽度成⽐比例，树的深度⼀一般是单个事务中所含项⺫⽬目数量的最⼤大值；树的宽度是平均每层所含项⺫⽬目的数量。由于在事务处理中通常会存在着⼤大量的共享频繁项，所以树的⼤大⼩小通常⽐比原数据库⼩小很多。频繁项集中的项以⽀支持度降序排列，⽀支持度越⾼高的项与FP-tree的根距离越近，因此有更多的机会共享结点，这进⼀一步保证了FP-tree的⾼高度压缩。

3.应⽤用：市场分析，沃尔玛市场案例：啤酒与尿布，数据挖掘中的关联规则挖掘4.优点：更快，效率更⾼高，能够处理⼤大数据

Trie 字典树

1.定义：⼜又称前缀树，是⼀一种哈希树的变种，是⼀一种有序树，⽤用于保存关联数组（映射），其中的键通常是字符串。与⼆二叉查找树不同，键不是直接保存在节点中，⽽而是由节点在树中的位置决定。⼀一个节点的所有⼦子孙都有相同的前缀，也就是这个节点对应的字符串，⽽而根节点对应空字符串。⼀一般情况下，不是所有的节点都有对应的值，只有叶⼦子节点和部分内部节点所对应的键才有相关的值。

trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，⽐比如⼀一串数字或者形状的排列。2.三个性质：

(1) 根节点不包含字符，除根节点外每⼀一个节点都只包含⼀一个字符

(2) 从根节点到某⼀一节点，路径上经过的字符连接起来，为该节点对应的字符串 (3) 每个节点的所有⼦子节点包含的字符都不相同 3.基本操作：查找、插⼊入、删除（⽐比较少⻅见）

4.时间复杂度：L是要搜索的前缀平均⻓长度，每次查找的时间复杂度是O(L) ；现在有N个前缀需要处理，那么整个时间复杂度就是O(N*L)；建字典树的时间复杂度，单词数为M，不妨设单词的平均⻓长度是L’，那么建字典树的时间复杂度就是O(M*L’)；所以整个算法的时间复杂度是O(N*L + M*L’)。

5.优点：利⽤用字符串的公共前缀来节约空间减少查询时间，最⼤大限度地减少⽆无谓的字符串⽐比较，时间复杂度是 O(n)，n 是要查询的单词中字⺟母个数，查询效率⽐比哈希树⾼高

6.缺点：trie树实际上是⼀一个DFA，通常⽤用转移矩阵表⽰示。⾏行表⽰示状态，列表⽰示输⼊入字符，（⾏行，列）位置表⽰示转移状态。这种⽅方式的查询效率很⾼高，但由于稀疏的现象严重，空间利⽤用效率很低。也可以采⽤用压缩的存储⽅方式即链表来表⽰示状态转移，但由于要线性查询，会造成效率低下。 7.改进：

(1)三数组Trie（Tripple-Array Trie）结构包括三个数组：base,next和check. (2)⼆二数组Trie（Double-Array Trie）包含base和check两个数组。base数组的每个元素表⽰示⼀一个Trie节点，即⼀一个状态；check数组表⽰示某个状态的前驱状态。 8.如何搜索字典项⺫⽬目？ (1) 从根结点开始⼀一次搜索

(2) 取得要查找关键词的第⼀一个字⺟母，并根据该字⺟母选择对应的⼦子树并转到该⼦子树继续进⾏行检索

(3) 在相应的⼦子树上，取得要查找关键词的第⼆二个字⺟母,并进⼀一步选择对应的⼦子树进⾏行检索 (4) 迭代

(5) 在某个结点处，关键词的所有字⺟母已被取出，则读取附在该结点上的信息，即完成查找 9.应⽤用：

(1)统计，排序和保存⼤大量的字符串（但不仅限于字符串），常被搜索引擎系统⽤用于⽂文本词频统计

(2)搜索提⽰示。如当输⼊入⼀一个⺴⽹网址，可以⾃自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回 前缀最相似的可能 (3)串的快速检索

给出N个单词组成的熟词表，以及⼀一篇全⽤用⼩小写英⽂文书写的⽂文章，请你按最早出现的顺序写出所有不在熟词表中的⽣生词。我们可以⽤用数组枚举，⽤用哈希，⽤用字典

树，先把熟词建⼀一棵树，然后读⼊入⽂文章进⾏行⽐比较，这种⽅方法效率是⽐比较⾼高的 (4)“串”排序

给定N个互不相同的仅由⼀一个单词构成的英⽂文名，让你将他们按字典序从⼩小到⼤大输出 。⽤用字典树进⾏行排序，采⽤用数组的⽅方式创建字典树，这棵树的每个结点的所有⼉儿⼦子很显然地按照其字⺟母⼤大⼩小排序。对这棵树进⾏行先序遍历即可。 (5)最⻓长公共前缀

对所有串建⽴立字典树，两个串的最⻓长公共前缀的⻓长度即是他们所在的结点的公共祖先个数，于是问题就转化为当时公共祖先问题。

Segment Tree 区间树

1.什么是区间树？

 区间树是在红⿊黑树基础上进⾏行扩展得到的⽀支持以区间为元素的动态集合的操作，其中每个节

点的关键值是区间的左端点。通过建⽴立这种特定的结构，可是使区间的元素的查找和插⼊入都可以在O(lgn)的时间内完成。相⽐比于基础的数据结构，增加了⼀一个max[x]，即以x为根的⼦子树中所有区间的端点的最⼤大值。

区间查找的并不是精确查找，⽽而是查找和给定区间重叠的元素。

2.区间查找

实现INTERVAL-SEARCH(T, i)，返回⼀一个和区间i重叠的区间，若⽆无，则返回nil[T]。基本思想

是我们通过左⼦子树的max进⾏行划分：如果左⼦子树的max值⼩小于low[i]，则左⼦子树不存在这样的

区间和i重叠，转到右⼦子树；否则，转到右⼦子树，因为左⼦子树的端点⼩小于右⼦子树，若左⼦子树⽆无可能，右⼦子树也必然不可能。

3.应⽤用场景

区间⽤用于表⽰示占⽤用⼀一连续时间段的⼀一些时间。通过查询⼀一个由时间区间数据构成的数据库，我们可以找到在给定的时间区间内发⽣生了什么事。在⾼高维的情况下，我们通过查询，可以分析⼀一张地图（⼆二维）、⼀一个场景（三维）中给定区域的特性。通过将区间存储在平衡⼆二叉搜索树中的⽅方式，我们可以在O（logn）时间内完成对区间的查询操作。

CAN 内容寻址⺴⽹网络

1.CAN是什么？

CAN是⼀一种P2P⺴⽹网络。P2P⺴⽹网络相对于服务器⺴⽹网络，服务器⺴⽹网络即所有节点链接在服务器上从服务器上获取信息，P2P⺴⽹网络中没有服务器只有平等的节点（Peer）。相对于服务器⺴⽹网络，P2P⺴⽹网络有更强的可扩展性和稳定性。每个节点都存储⼀一部分信息（Value），节点间互相连接，形成⼀一个连通图，⼀一个节点需要某个Value时便遍历周围节点，直到找到所需Value为⽌止。如果进⼀一步将各节点构成的连通图抽象化为某种结构以便于管理，便成为了结构化P2P⺴⽹网络，CAN是其中⼀一种。

2.CAN的思想：每个节点都是n维坐标空间中的⼀一块⼉儿区域，下⾯面是⼀一个有4个节点的2维哈希表的例⼦子：

节点位于哪个位置由其key值Hash后得到，因此想知道你想要的Value在哪，只要将其key

值Hash⼀一下即可，接下来只需要找到连接到该节点需要经过的中间节点就可进⾏行访问得

到Value。⽽而每个节点除了Value和Key之外还存储有与其相邻节点的Key值，从⽽而可以实现中间结点的寻找。3.改进

a)增加CAN的维数

b)允许多个节点共享同⼀一块⼉儿区域 c)设置多个坐标空间，提⾼高了容错性

Hash Table

将数据的Key值通过Hash函数映射到存储空间的某个位置，因此通过Key值即可直接访问数据，提⾼高了访问速度。

Hash函数即将Key变换为存储地址的函数，最常⽤用的⽅方法如除留余数法。

不同的Key值可能得到相同的地址，这便是产⽣生了冲突，如何解决冲突是Hash表要解决的⼀一

个重要问题，主要有两种：

a) 链接法（开散列法）：将相同地址的数据⽤用链表连接起来。

b) 开放寻址（闭散列法）：当⼀一个地址已经被占⽤用时，为下⼀一个Hash到此地址的数据通

过某种⽅方法寻找下⼀一个地址，常⽤用⽅方法有三种：

i. 线性探查（沿着地址空间⼀一个挨⼀一个往下找空地址）

ii. ⼆二次探查

iii. 双重散列

Huffman Code

哈夫曼树⼜又称最优⼆二叉树，  是⼀一种带权路径⻓长度最短的⼆二叉树。所谓树的带权路径⻓长度，

就是树中所有的叶结点的权值乘上其到根结点的 路径⻓长度（若根结点为0层，叶结点到根结

点的路径⻓长度为叶结点的层数）。树的带权路径⻓长度记为WPL=

(W1*L1+W2*L2+W3*L3+...+Wn*Ln)  ，N个权值Wi(i=1,2,...n)构成⼀一棵有N个叶结点的⼆二叉树，相应的叶结点的路径⻓长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最⼩小的。处理⼀一个n个字符的字⺟母表C需要花费时间O(nlgn)。

哈夫曼编码步骤：

⼀一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵⼆二叉树的初始集合F=

{T1,T2,T3,...,Ti,...,Tn}，其中每棵⼆二叉树Ti中只有⼀一个权值为Wi的根结点，它的左右⼦子树均为空。（为⽅方便在计算机上实现算 法，⼀一般还要求以Ti的权值Wi的升序排列。）

⼆二、在F中选取两棵根结点权值最⼩小的树作为新构造的⼆二叉树的左右⼦子树，新⼆二叉树的根结点的权值为其左右⼦子树的根结点的权值之和。

三、从F中删除这两棵树，并把这棵新的⼆二叉树同样以升序排列加⼊入到集合F中。四、重复⼆二和三两步，直到集合F中只有⼀一棵⼆二叉树为⽌止。哈弗曼编码会构造最优前缀码。

Lossy Counting 有损计数

挖掘数据流的频繁项是⼀一个具有挑战性的问题.由于数据流具有⽆无限性的特点,算法只能

⼀一遍扫描数据.通 过⼀一遍扫描数据流来计算精确的频繁项,⾄至少需要 O(M)的存储空间,M 为数据流中出现的所有不同值的集合, 可能是⽆无穷的.于是,准确挖掘数据流中的频繁项通常是不可能的.因此,⼈人们主要关注挖掘数据流频繁项近似算法。挖掘数据流频繁项近似算法的特点是⼀一遍扫描,只使⽤用很少的存储空间,查询结果虽然是真实结果的 近似,但算法可以保证近似查询

结果与真实结果之间的误差不超过⽤用户指定的区间范围.

Lossy Counting算法的基本思想是:在主存中维护数据流的⼀一个样本集合,每当数据流到来⼀一个 数据项,若其值已经出现在样本集合中,则将相应的计数器加 1;否则,将新到的数据项以及该数据项此前在数据 流中出现频率的上界(估计值)加⼊入到样本集合中.数据流每到来 1/ε个数据项,Lossy Counting 算法对样本集合 进⾏行⼀一次扫描,删除其中频率低于εN 的样本。

严晟嘉  焦晨航  著于  2015.6.17