关于数据:关于数据存储引擎结构没有比这篇更详细的

摘要：常见存储算法构造涵盖：哈希存储，B、B+、B* 树存储，LSM 树存储引擎，R 树，倒排索引，矩阵存储，对象与块，图构造存储等等。

介绍

在存储系统的设计中，存储引擎属于底层数据结构，间接决定了存储系统所可能提供的性能和性能。常见存储算法构造涵盖：哈希存储，B、B+、B* 树存储，LSM 树存储引擎，R 树，倒排索引，矩阵存储，对象与块，图构造存储等等。

哈希存储引擎是哈希表的长久化实现，个别用于键值类型的存储系统。而大多传统关系型数据库应用索引来辅助查找数据，用以减速对数据库数据的拜访。思考到常常须要范畴查找，因而其索引个别应用树型构造。譬如 MySQL、SQL Server、Oracle 中，数据存储与索引的根本构造是 B - 树和 B + 树。

支流的 NoSQL 数据库则应用日志构造合并树 (Log-structured Merge Tree) 来组织数据。LSM 树存储引擎和 B 树一样，反对增、删、改、随机读取以及程序扫描。通过批量转储技术躲避磁盘随机写入问题，极大地改善了磁盘的 IO 性能, 被广泛应用于后盾存储系统，如 Google Big table、Level DB，Facebook Cassandra 零碎，开源的 HBase，Rocks dB 等等。

……

一．哈希存储

哈希存储的根本思维是以关键字 Key 为自变量，通过肯定的函数关系(散列函数或哈希函数），计算出对应函数值（哈希地址），以这个值作为数据元素的地址，并将数据元素存入到相应地址的存储单元中。查找时再依据要查找的关键字采纳同样的函数计算出哈希地址，而后间接到相应的存储单元中去取要找的数据元素。代表性的应用方包含 Redis，Memcache，以及存储系统 Bitcask 等。

基于内存中的 Hash, 反对随机的增删改查，读写的工夫复杂度 O(1)。但无奈反对程序读写(指典型 Hash，不包含如 Redis 的基于跳表的 ZSet 的其它性能), 在不须要有序遍历时，性能最优。

1. 罕用哈希函数

结构哈希函数的总的准则是尽可能将关键字汇合空间平均的映射到地址汇合空间中，同时尽可能升高抵触产生的概率。

• 除留余数法:H(Key)=key % p (p ≤ m)p 最好抉择一个小于或等于 m(哈希地址汇合的个数)的某个最大素数。
• 间接地址法: H(Key) =a * Key + b；“a，b”是常量。
• 数字分析法

比方有一组 key1=112233，key2=112633，key3=119033，剖析数两头两个数比拟稳定，其余数不变。那么取 key 的值就能够是 key1=22,key2=26,key3=90。

• 平方取中法
• 折叠法

比方 key=135790，要求 key 是 2 位数的散列值。那么将 key 变为 13+57+90=160，而后去掉高位“1”, 此时 key=60。

2. 抵触解决办法

1) 凋谢地址法

如果两个数据元素的哈希值雷同，则在哈希表中为后插入的数据元素另外抉择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到合乎查找要求的数据元素，程序就会持续往后查找，直到找到一个合乎查找要求的数据元素，或者遇到一个空的表项。

①. 线性探测法

这种办法在解决抵触时，顺次探测下一个地址，直到有空的地址后插入，若整个空间都找遍依然找不到空余的地址，产生溢出。Hi =(H(Key) + di ) % m (i = 1,2,3,…,k , k ≤ m-1)

地址增量 di = 1,2,…, m-1, 其中 i 为探测次数

②. 二次探测法

地址增量序列为: di= 1^2，-1^2，2^2，-2^2，…，q^2，-q^2 (q≤ m/2）

Python 字典 dict 的实现是应用二次探查来解决抵触的。

③. 双哈希函数探测法

Hi =(H(Key) + i * RH(Key) ) % m (i=1,2,3,…, m-1)

H(Key) , RH(Key) 是两个哈希函数，m 为哈希表长度。先用第一个哈希函数对关键字计算哈希地址，一旦产生地址抵触，再用第二个函数确定挪动的步长因子，最初通过步长因子序列由探测函数寻找空余的哈希地址。H1= (a +b) % m, H2 = (a + 2b) % m, …, Hm-1= (a+ (m-1)*b) %m

2) 链地址法

将哈希值雷同的数据元素寄存在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采纳线性查找办法。

Hash 存储示例

假设一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70), 散列地址空间为 HT[13]，采纳除留余数法结构散列函数和线性探测法解决抵触。

二．B 树存储引擎

B 树存储引擎是 B 树的长久化实现，不仅反对单条记录的增、删、读、改操作，还反对程序扫描（B+ 树的叶子节点间的指针）。相比哈希存储引擎，B 树存储引擎不仅反对随机读取，还反对范畴扫描。Mysql 的 MyISAM 和 InnoDB 反对 B - 树索引,InnoDB 还反对 B + 树索引，Memory 反对 Hash。

1. B- 树存储

B- 树为一种多路均衡搜寻树，与红黑树最大的不同在于，B 树的结点能够有多个子节点，从几个到几千个。B 树与红黑树类似，一棵含 n 个结点的 B 树的高度也为 O(lgn)，但可能比一棵红黑树的高度小许多，因为它的分支因子比拟大。所以 B 树可在 O(logn)工夫内，实现各种如插入，删除等动静汇合操作。

B- 树的规定定义：

1) 定义任意非叶子节点最多能够有 M 个儿子节点；且 M >2；

2) 则根节点的儿子数为：[2，M]；

3) 除根节点为的非叶子节点的儿子书为[M/2，M]；

4) 每个结点寄存至多 M /2-1(取上整)且至少 M -1 个关键字；(至多为 2)

5) 非叶子结点的关键字个数 = 指向子节点的指针书 -1；

6) 非叶子节点的关键字：K[1],K[2],K[3],…,K[M-1; 且 K[i] < K[i +1];

7) 非叶子结点的指针：P[1], P[2], …, P[M]；其中 P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于 K[M-1]的子树，其它 P[i]指向关键字属于 (K[i-1], K[i]) 的子树；

8) 所有叶子结点位于同一层；

下图是一个 M 为 3 的 B - 树：

B- 树的搜寻

从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则完结，否则进入查问关键字所属范畴的儿子结点；反复，直到所对应的儿子指针为空，或曾经是叶子结点；

B- 树的个性

关键字汇合散布在整颗树中, 任何一个关键字呈现且只呈现在一个结点中；

所有结点都存储数据，搜寻有可能在非叶子结点完结；

搜寻性能等价于在关键字选集内做一次二分查找, 查问工夫复杂度不固定，与 Key 在树中的地位无关，最好为 O(1)；

非叶子节点存储了 data 数据，导致数据量很大的时候，树的层数可能会比拟高，随着数据量减少，IO 次数的管制不如 B + 树优良。

MongoDB 存储构造

MongoDB 是聚合型数据库，而 B - 树恰好 Key 和 data 域聚合在一起，所有节点都有 Data 域，只有找到指定索引就能够进行拜访，无疑单次查问均匀快于 MySql。

MongoDB 并不是传统的关系型数据库，而是以 Json 格局作为存储的 NoSQL, 目标就是高性能、高可用、易扩大。

1. B+ 树存储

B 树在进步磁盘 IO 性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+ 树应运而生。B+ 树是对 B 树的一种变形，实质还是多路均衡查找树。B+ 树只有遍历叶子节点就能够实现整棵树的遍历。而且在数据库中基于范畴的查问是十分频繁的，而 B 树不反对这样的操作(或者说效率太低)。RDBMS 须要 B + 树用以缩小寻道工夫，程序拜访较快。

B+ 树通常被用于数据库和操作系统的文件系统中。像 NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和 BFS 等文件系统都在应用 B + 树作为元数据索引。B+ 树的特点是可能保持数据稳固有序，其插入与批改领有较稳固的对数工夫复杂度。B+ 树元素为自底向上插入。

下图是一棵高度为 M = 3 的 B + 树

B+ 树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点 (即数据节点) 之间是一种链式环构造。因而能够对 B + 树进行两种查找运算：一种是对于主键的范畴查找和分页查找，另一种是从根节点开始，进行随机查找。

与一般 B - 树相比，B+ 树的非叶子节点只有索引，所有关键字都位于叶子节点，这样会使树节点的度比拟大，而树的高度就比拟低，从而有利于进步查问效率。并且叶子节点上的数据会造成有序链表。

次要长处如下：

• 构造比拟扁平，高度低(个别不超过 4 层)，随机寻道次数少；
• 有 n 棵子树的结点中含有 n 个关键字，不用来保留数据，只用来索引。结点中仅含其子树（根结点）中的最大（或最小）关键字。
• 数据存储密度大，且都位于叶子节点，查问稳固，遍历不便；
• 叶子节点寄存数值，依照值大小程序排序，造成有序链表，区间查问转化为程序读，效率高。且所有叶子节点与根节点的间隔雷同，因而任何查问效率都很类似。而 B 树则必须通过中序遍历才反对范畴查问。
• 与二叉树不同，B+ 树的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比拟小的代价实现自均衡。

B+ 树的毛病：

• 如果写入的数据比拟离散，那么寻找写入地位时，子节点有很大可能性不会在内存中，最终产生大量随机写，性能降落。下图阐明了这一点。

• B+ 树在查问过程中应该不会慢，但如 B + 树已运行很长时间，写入了很多数据，随着叶子节点决裂，其对应的块会不再顺序存储而变得扩散, 可能会导致逻辑上本来间断的数据实际上寄存在不同的物理磁盘块地位上，这时执行范畴查问也会变成随机读，会导致较高的磁盘 IO, 效率升高。

譬如：数据更新或者插入齐全无序时，如先插入 0，后 80000，而后 200，而后 666666，这样跨度很大的数据时，因为不在一个磁盘块中，就需先去查找到这个数据。数据十分离散，就意味着每次查找时，它的叶子节点很可能都不在内存中，此时就会呈现性能的瓶颈。并且随机写产生的子树的决裂等，产生很多的磁盘碎片，也是不太敌对的一面。

可见 B + 树在多读少写（相对而言）的情境下比拟有劣势。当然，可用 SSD 来取得成倍晋升的读写速率，但老本绝对较高。

B+ 树的搜寻

与 B - 树基本相同，区别是 B + 树只有达到叶子结点才命中(B- 树可在非叶子结点命中)，其性能也等价于在关键字选集做一次二分查找。

B+ 树的个性

非叶子结点相当于是叶子结点的索引 (稠密索引)，叶子结点相当于是存储(关键字) 数据的数据层；B+ 树的叶子结点都是相链的，因而对整棵树的遍历只须要一次线性遍历叶子结点即可。而且因为数据顺序排列并且相连，所以便于区间查找和搜寻。而 B - 树则须要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有 B + 树好。

比 B - 树更适宜理论利用中操作系统的文件索引和数据库索引

1) 磁盘读写代价更低

B+ 树的外部结点并没有指向关键字具体信息的指针。因而其外部结点绝对 B 树更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来说 IO 读写次数也就升高了。

举个例子，假如磁盘中的一个盘块包容 16bytes，而一个关键字 2bytes，一个关键字具体信息指针 2bytes。一棵 9 阶 B -tree(一个结点最多 8 个关键字)的外部结点须要 2 个盘快。而 B + 树外部结点只须要 1 个盘快。当须要把外部结点读入内存中的时候，B 树就比 B + 树多一次盘块查找时间。

2）查问效率更加稳固

因为非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当。

MySQL InnoDB

InnoDB 存储引擎中页大小为 16KB，个别表的主键类型为 INT(占用 4 字节)或 long(8 字节)，指针类型也个别为 4 或 8 个字节，也就是说一个页 (B+ 树中的一个节点) 中大略存储 16KB/(8B+8B)=1K 个键值(K 取估值为 10^3)。即一个深度为 3 的 B + 树索引可保护 10^3 10^3 10^3=10 亿条记录。

在数据库中，B+ 树的高度个别都在 2~4 层。MySql 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只须要 1~3 次磁盘 I / O 操作。

数据库中的 B + 树索引能够分为汇集索引 (clustered index) 和辅助索引(secondary index)。汇集索引的 B + 树中的叶子节点寄存的是整张表的行记录数据。辅助索引与汇集索引的区别在于辅助索引的叶子节点并不蕴含行记录的全副数据，而是存储相应行数据的汇集索引键，即主键。当通过辅助索引来查问数据时，InnoDB 存储引擎会遍历辅助索引找到主键，而后再通过主键在汇集索引中找到残缺的行记录数据。

3. B* 树存储

B+ 树的一种变形，在 B + 树的根底上将索引层以指针连接起来，使搜寻取值更加快捷。如下图(M=3)

绝对 B + 树的变动，如下：

• B树定义了非叶子结点关键字个数至多为(2/3)M，即块的最低使用率为 2 / 3 代替 B + 树的 1 /2，将结点的最低利用率从 1 / 2 进步到 2 /3；
• B+ 树的决裂: 当一个结点满时调配一个新的结点，并将原结点中 1 / 2 的数据复制到新结点，最初在父结点中减少新结点的指针；B+ 树的决裂只影响原结点和父结点，而不影响兄弟结点，所以它不需指向兄弟的指针；
• B* 树的决裂: 当一个结点满时，如它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最初批改父结点中兄弟结点的关键字(因兄弟结点的关键字范畴扭转), 如兄弟也满了, 则在原结点与兄弟结点之间减少新结点, 并各复制 1 / 3 数据到新结点, 最初在父结点减少新结点的指针.

绝对于 B + 树，B* 树调配新结点的概率比 B + 树要低，空间利用率、查问速率也有所提高。

三．LSM 树存储引擎

数据库的数据大多存储在磁盘上，无论是机械硬盘还是固态硬盘(SSD)，对磁盘数据的程序读写速度都远高于随机读写。大量的随机写，导致 B 树在数据很大时，呈现大量磁盘 IO，速度越来越慢，基于 B 树的索引构造是违反上述磁盘根本特点的—需较多的磁盘随机读写。于是，基于日志构造的新型索引构造办法应运而生, 次要思维是将磁盘看作一个大的日志，每次都将新的数据及其索引构造增加到日志的最末端，以实现对磁盘的程序操作，从而进步索引性能。

对海量存储集群而言，LSM 树也是作为 B + 树的代替计划而产生。当今很多支流 DB 都应用了 LSM 树的存储模型，包含 LevelDB，HBase，Google BigTable，Cassandra，InfluxDB, RocksDB 等。LSM 树通过尽可能减少写磁盘次数，理论落地存储的数据按 key 划分，造成有序的不同文件；联合其“先内存更新后合并落盘”的机制，尽量达到程序写磁盘，尽可能减少随机写；对于读则需合并磁盘已有历史数据和以后未落盘的驻于内存的更新。LSM 树存储反对有序增删改查，写速度大幅提高，但随机读取数据时效率低。

LSM 树理论不是一棵树，而是 2 个或者多个树或相似树的构造的汇合。

下图为蕴含 2 个构造的 LSM 树

在 LSM 树中，最低一级即最小的 C0 树位于内存, 而更高级的 C1、C2… 树都位于磁盘里。数据会先写入内存中的 C0 树，当它的大小达到肯定阈值之后，C0 树中的全副或局部数据就会刷入磁盘中的 C1 树，如下图所示。

因为内存读写速率比外存要快十分多，因而数据写入 C0 树的效率很高。且数据从内存刷入磁盘时是预排序的，也就是说，LSM 树将本来随机写操作转化成了程序写操作，写性能大幅晋升。不过，它的 tradeoff 就是就义了一部分读性能，因为读取时需将内存中数据和磁盘中的数据合并。总体上讲这种衡量还是值得的, 因为：

• 能够先读取内存中 C0 树的缓存数据。内存效率高且依据局部性原理，最近写入的数据命中率也高。
• 写入数据未刷到磁盘时不会占用磁盘的 I /O，不会与读取竞争。读取操作就能获得更长的磁盘工夫，变相地补救了读性能差距。

在理论利用中，为避免内存因断电等起因失落数据，写入内存的数据同时会程序在磁盘上写日志，相似于预写日志(WAL)，这就是 LSM 这个词中 Log 一词的来历。另外，如有多级树，低级的树在达到大小阈值后也会在磁盘中进行合并，如下图所示。

1. Leveldb/Rocksdb

根本形容

1) 对数据，按 key 划分为若干 level，每个 level 对应若干文件，包含存在于内存中和落盘的。文件内 key 都有序，同级的各个文件之间个别也有序，level0 对应于内存中的数据(0.sst)，前面顺次是 1、2、3、… 的各级文件(默认到 level6)。

2) 写时，先写对应内存的最低 level 的文件，这也是快的一个起因。内存的数据也是被长久化的，达到肯定大小后被合并到下一级文件落盘。

3) 落盘后的各级文件也会定期进行排序加合并，合并后数据进入下一层 level；这样的写入操作，大多数都是对一个页程序的写，或者申请新页写，而不再是随机写。

Rocksdb Compact

Compact 是个很重要的步骤，上面是 rocksdb 的 compact 过程：

Rocksdb 的各级文件组织模式：

各级的每个文件，外部都按 key 有序，除了内存对应的 level0 文件，外部文件之间也是按 key 有序；这样查找一个 key，很不便二分查找。

而后，当每一级的数据达到肯定阈值时，会触发排序归并，简略说，就是在两个 level 的文件中，把 key 有重叠的局部，合并到高层 level 的文件里

这个在 LSM 树里叫数据压缩(compact)；

对于 Rocksdb，除了内存 level0 到 level1 的 compact，其余各级之间的 compact 能够并行；通常设置较小的 level0 到 level1 的 compact 阈值，放慢这一层的 compact。良好的归并策略的配置，使数据尽可能集中在最高层(90% 以上)，而不是中间层，这样有利于 compact 的速度；另外，对于基于 LSM 树的读，须要在各级文件中二分查找，磁盘 IO 也不少，此外还须要关注 level0 里的对于这个 key 的操作，比拟显著的优化是，通过 Bloomfilter 略掉必定不存在该 key 的文件，缩小无谓查找；

1. HBase LSM

阐明：本大节需当时理解 HBase 的读写流程及 MemStore。

MemStore 作为列族级别的写入和读取缓存，它就是 HBase 中 LSM 树的 C0 层。它未采纳树形构造来存储，而是采纳了跳表(一种代替自均衡 BST 二叉排序树的构造)。MemStore Flush 的过程，也就是 LSM 树中 C0 层刷写到 C1 层的过程，而 LSM 中的日志对应到 HBase 天然就是 HLog 了。

HBase 读写流程简图

HFile 就是 LSM 树中的高层实现。从逻辑上来讲，它是一棵满的 3 层 B + 树，从上到下的 3 层索引别离是 Root index block、Intermediate index block 和 Leaf index block，对应到上面的 Data block 就是 HFile 的 KeyValue 构造。HFile V2 索引构造的图示如下：

HFile 过多会影响读写性能，因而高层 LSM 树的合并即对应 HFile 的合并 (Compaction) 操作。合并操作又分 Minor 和 Major Compaction，因为 Major Compaction 波及整个 Region，对磁盘压力很大, 因而要尽量避免。

布隆过滤器(Bloom Filter)

是保留在内存中的一种数据结构，可用来验证“某样货色肯定不存在或者可能存在”。由一个超长的二进制位数组和一系列的 Hash 函数组成，二进制位数组初始全副为 0，当有元素退出汇合时，这个元素会被一系列 Hash 函数计算映射出一系列的值，所有的值在位数组的偏移量处理为 1。如需判断某个元素是否存在于汇合中，只需判断该元素被 Hash 后的值在数组中的值，如果存在为 0 的则该元素肯定不存在；如果全为 1 则可能存在，这种状况可能有误判。

HBase 为了晋升 LSM 构造下的随机读性能而引入布隆过滤器(建表语句中可指定)，对应 HFile 中的 Bloom index block，其结构图如下。

通过布隆过滤器，HBase 能以大量的空间代价，换来在读取数据时十分疾速地确定是否存在某条数据，效率进一步晋升。

LSM- 树的这种构造十分有利于数据的疾速写入(实践上可靠近磁盘程序写速度），但不利于读, 因为实践上读的时候可能须要同时从 memtable 和所有硬盘上的 sstable 中查问数据，这样显然会对性能造成较大影响。为解决这个问题，LSM- 树采取以下次要相干措施。

• 定期将硬盘上小的 sstable 合并 (Merge 或 Compaction) 成大的 sstable，以缩小 sstable 的数量。且平时的数据更新删除操作并不会更新原有的数据文件，只会将更新删除操作加到以后的数据文件末端，只有在 sstable 合并的时候才会真正将反复的操作或更新去重、合并。
• 对每个 sstable 应用布隆过滤器, 以减速对数据在该 sstable 的存在性进行断定, 从而缩小数据的总查问工夫。

SSTable(Sorted String Table)

当内存中的 MemTable 达到肯定大小，需将 MemTable 转储 (Dump) 到磁盘中生成 SSTable 文件。因为数据同时存在 MemTable 和可能多个 SSTable 中，读取操作需按从旧到新的工夫程序合并 SSTable 和内存中的 MemTable 数据。

SSTable 中的数据按主键排序后寄存在间断的数据块 (Block) 中，块之间也有序。接着，存放数据块索引，由每个 Block 最初一行的主键组成，用于数据查问中的 Block 定位。接着寄存布隆过滤器和表格的 Schema 信息。最初寄存固定大小的 Trailer 以及 Trailer 的偏移地位。

实质上看，SSTable 是一个两级索引构造：块索引以及行索引。分为稠密格局和浓密格局。对于稠密格局，某些列可能存在也可能不存在，因而每一行只存储蕴含理论值的列，每一列存储的内容为：< 列 ID，列值 >; 而浓密格局中每一行都需存储所有列，每一列只需存储列值，不需存储列 ID，列 ID 可从表格 Schema 中获取。

… …

1. 图库 ArangoDB LSM

ArangoDB 采纳 RocksDB 做底层存储引擎，RocksDB 应用 LSM-Tree 数据结构。

存储的格局十分相似 JSON，叫做 VelocyPack 格局的二进制格局存储。

（1）文档被组织在汇合中。

（2）有两种汇合：文档（V），边汇合（E）

（3）边汇合也是以文档模式存储，但蕴含两个非凡的属性_from 和_to，被用来创立在文档和文档之间创立关系

索引类型

· Primary Index，默认索引，建设字段是_key 或_id 上，一个哈希索引

· Edge Index，默认索引，建设在_from、_to 上，哈希索引；不能用于范畴查问、排序，弱于 OrientDB

· Hash Index，自建

· Skiplist Index，有序索引，

o 用于疾速查找具备特定属性值的文档，范畴查问以及按索引排序，程序返回文档。

o 用于查找，范畴查问和排序。补全范畴查问的毛病。

· Persistent Index，RocksDB 的索引。

o 持久性索引是具备持久性的排序索引。当存储或更新文档时，索引条目将写入磁盘。

o 应用持久性索引可能会缩小汇合加载工夫。

· Geo Index，能够在汇合中的一个或多个属性上创立其余天文索引。

· Fulltext Index，全文索引

四．R 树的存储构造

R 树是 B 树在高维空间的扩大，是一棵均衡树。每个 R 树的叶子结点蕴含了多个指向不同数据的指针，这些数据能够是寄存在硬盘中，也可存在内存中。依据 R 树的这种数据结构，当需进行一个高维空间查问时，只须要遍历少数几个叶子结点所蕴含的指针，查看这些指针指向的数据是否满足即可。这种形式使得不用遍历所有数据即可取得答案，效率显著进步。

下图是 R 树的一个简略实例：

R 树使用空间宰割理念，采纳一种称为 MBR(Minimal Bounding Rectangle)的办法，在此译作“最小边界矩形”。从叶子结点开始用矩形将空间框起来，结点越往上，框住的空间就越大，以此对空间进行宰割。

以二维空间举例, 下图是 Guttman 论文中的一幅图：

1) 首先假如所有数据都是二维空间下的点，图中仅仅标记了 R8 区域中的数据，也就是那个 shape of data object。别把那一块不规则图形看成一个数据，把它看作是多个数据围成的一个区域。为了实现 R 树结构，用一个最小边界矩形恰好框住这个不规则区域，这样就结构出了一个区域：R8。R8 的特点很显著，就是正好框住所有在此区域中的数据。其余实线包围住的区域，如 R9，R10，R12 等都是同样情理。这样一共失去了 12 个最最根本的最小矩形。这些矩形都将被存储在子结点中。

2) 下一步操作就是进行高一档次的解决, 发现 R8，R9，R10 三个矩形间隔最为凑近，因而就能够用一个更大的矩形 R3 恰好框住这 3 个矩形。

3) 同样，R15，R16 被 R6 恰好框住，R11，R12 被 R4 恰好框住，等等。所有最根本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。

用地图和餐厅的例子来解释，就是所有的数据都是餐厅所对应的地点，先把相邻的餐厅划分到同一块区域，划分好所有餐厅之后，再把邻近的区域划分到更大的区域，划分结束后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止。要查找的时候就不便了。

而后就能够把这些大大小小的矩形存入 R 树中。根结点寄存的是两个最大的矩形，这两个最大的矩形框住了所有的残余的矩形，当然也就框住了所有的数据。下一层的结点寄存了次大的矩形，这些矩形放大了范畴。每个叶子结点都是寄存的最小的矩形，这些矩形中可能蕴含有 n 个数据。

查问特定的数据

以餐厅为例，假如查问广州市天河区天河城左近一公里的所有餐厅地址

1) 关上地图(即整个 R 树)，先抉择国内还是国外(根结点);

2) 而后抉择华南地区(对应第一层结点)，抉择广州市(对应第二层结点);

3) 再抉择天河区（对应第三层结点）;

4) 最初抉择天河城所在的那个区域(对应叶子结点，寄存有最小矩形)，遍历所有在此区域内的结点，看是否满足要求即可。

其实 R 树的查找规定跟查地图很像，对应下图：

一棵 R 树满足如下性质：

1) 除非它是根结点之外，所有叶子结点蕴含有 m 至 M 个记录索引(条目)。作为根结点的叶子结点所具备的记录个数能够少于 m。通常，m=M/2。

2) 对于所有在叶子中存储的记录(条目)，I 是最小的能够在空间中齐全笼罩这些记录所代表的点的矩形(此处所说“矩形”是可扩大到高维空间)。

3) 每一个非叶子结点领有 m 至 M 个孩子结点，除非它是根结点。

4) 对于在非叶子结点上的每一个条目，i 是最小的可在空间上齐全笼罩这些条目所代表的店的矩形(同性质 2)

5) 所有叶子结点都位于同一层，因而 R 树为均衡树。

阐明：

叶子结点的构造，数据模式为: (I, tuple-identifier)，tuple-identifier 示意的是一个寄存于数据库中的 tuple，也就是一条记录，是 n 维的。I 是一个 n 维空间的矩形，并可恰好框住这个叶子结点中所有记录代表的 n 维空间中的点。I=(I0,I1,…,In-1)。

R 树是一种可能无效进行高维空间搜寻的数据结构，已被广泛应用在各种数据库及其相干的利用中。但 R 树的解决也具局限性，它的最佳利用范畴是解决 2 至 6 维的数据，更高维的存储会变得非常复杂，这样就不实用。近年来，R 树也呈现了很多变体，R* 树就是其中的一种。这些变体晋升了 R 树的性能，如需更多理解，能够参考相干文献。

利用示例

天文围栏 (Geo-fencing) 是 LBS(Location Based Services)的一种利用，就是用一个虚构的栅栏围出一个虚构天文边界，当手机进入、来到某个特定天文区域，或在该区域内流动时，手机能够接管主动告诉和正告。譬如，假如地图上有三个商场，当用户进入某个商场的时候，手机主动收到相应商场发送的优惠券 push 音讯。天文围栏利用十分宽泛，当今挪动互联网次要 app 如美团、公众点评、手淘等都可看到其利用身影。

五．倒排索引存储

对 Mysql 来说，采纳 B + 树索引，对 Elasticsearch/Lucene 来说，是倒排索引。倒排索引 (Inverted Index) 也叫反向索引，有反向索引必有正向索引。艰深地讲，正向索引是通过 key 找 value，反向索引则是通过 value 找 key。

Elasticsearch 是建设在全文搜索引擎库 Lucene 根底上的搜索引擎，它暗藏了 Lucene 的复杂性，提供一套简略统一的 RESTful API。Elasticsearch 的倒排索引其实就是 Lucene 的倒排索引。

1. Lucene 的倒排索引

倒排索引，通过 Term 搜寻到文档 ID。首先想想看，世界上那么多单词，中文、英文、日文、韩文 … 如每次搜寻一个单词都要全局遍历一遍，显著不行。于是有了对单词进行排序，像 B + 树一样可在页里实现二分查找。光排序还不行，单词都放在磁盘，磁盘 IO 慢的不得了，大量寄存内存会导致内存爆了。

下图：通过字典把所有单词都贴在目录里。

Lucene 的倒排索引，减少了最右边的一层「字典树」term index，它不存储所有的单词，只存储单词前缀，通过字典树找到单词所在的块，也就是单词的大略地位，再在块里二分查找，找到对应的单词，再找到单词对应的文档列表。

假如有多个 term，如：Carla,Sara,Elin,Ada,Patty,Kate,Selena。找出某个特定 term, 可通过排序后以二分查找形式，logN 次磁盘查找失去指标，但磁盘随机读操作较低廉(单次 Random access 约 10ms)。所以尽量少的读磁盘，可把一些数据缓存到内存。但 term dictionary 太大，于是就有了 term index. 通过 trie 树来构建 index;

通过 term index 可疾速定位 term dictionary 的某个 offset，从这个地位再往后程序查找。再加上一些压缩技术(FST)，term index 的尺寸能够只有所有 term 尺寸的几十分之一，使得用内存缓存整个 term index 变成可能。

FST Tree

一种无限状态转移机，长处：1）空间占用小。通过对词典中单词前缀和后缀的反复利用，压缩了存储空间；2）查问速度快。O(len(str))的查问工夫复杂度。

示例：对“cat”、“deep”、“do”、“dog”、“dogs”这 5 个单词进行插入构建 FST（必须已排序），失去如下一个有向无环图。

FST 压缩率个别在 3 倍~20 倍之间，绝对于 TreeMap/HashMap 的收缩 3 倍，内存节俭就有 9 倍到 60 倍！

1. 与 MySQL 检索比照

MySQL 只有 term dictionary，以 B - 树排序的形式存储在磁盘上。检索一个 term 需若干次 random access 磁盘操作。而 Lucene 在 term dictionary 的根底上增加了 term index 来减速检索，以树的模式缓存在内存中。从 term index 查到对应 term dictionary 的 block 地位后，再去磁盘上找 term，大大减少磁盘的 random access 次数。

Term index 在内存中是以 FST(finite state transducers)的压缩模式保留，其特点是十分节俭内存。Term dictionary 在磁盘上是以分 block 的形式保留的，一个 block 外部利用公共前缀压缩，比方都是 Ab 结尾的单词就能够把 Ab 省去。这样 term dictionary 可比 B - 树更节约空间。

1. 联结索引构造及检索

给定多个查问过滤条件，如”age=18 AND gender= 女”就是把两个 posting list 做一个“与”的合并。对于 MySql 来说，如果给 age 和 gender 两个字段都建设了索引，查问时只会抉择其中最 selective 的来用，而后另一个条件是在遍历行的过程中在内存中计算之后过滤掉。那如何联结应用两个索引呢？两种方法：

• 应用 skip list 数据结构，同时遍历 gender 和 age 的 posting list，相互 skip；
• 应用 bitset 数据结构，对 gender 和 age 两个 filter 别离求出 bitset，对两个 bitset 做 AND 操作。

PostgreSQL 从 8.4 版本开始反对通过 bitmap 联结应用两个索引，就是利用 bitset 数据结构来做的。一些商业的关系型数据库也反对相似联结索引的性能。

ES 反对以上两种的联结索引形式，如果查问的 filter 缓存到了内存中(以 bitset 模式），那么合并就是两个 bitset 的 AND。如果查问的 filter 没有缓存，那么就用 skip list 的形式去遍历两个 on disk 的 posting list。

1) 利用 Skip List 合并

即便对于排过序的链表，查找还是须要进行通过链表的指针进行遍历，工夫复杂度很高仍然是 O(n)，这个显然不能承受。是否能够像数组那样，通过二分法查找，但因为在内存中的存储的不确定性，不能这么做。但可联合二分法思维，跳表就是链表与二分法的联合。跳表是有序链表。

• 链表从头节点到尾节点都是有序的
• 能够进行跳跃查找(形如二分法），升高工夫复杂度

阐明：在上图中如要找 node6 节点

1) 第一次比拟 headerNode->next[2]的值，即 node5 的值。显然 node5 小于 node6，所以，下一次应从第 2 级的 node5 开始查问，令 targetNode=targetNode->next[2];

2) 第二次应该比拟 node5->next[2]的值，即 tailNode 的值。tailNode 的值是最大的，所以后果是大于，下一次应从第 1 级的 node5 开始查问。这里从第 2 级跳到第 1 级。但没有扭转 targetNode。

3) 第三次应该比拟 node5->next[1]的值，即 node7 的值。因 node7 大于 node6，所以，下一次应该从第 0 级的 node5 开始查问。这里从第 1 级跳到第 0 级。也没有扭转 targetNode。

4) 第四次应该比拟 node5->next[0]的值，即 node6 的值。这时相等，完结。如果小于，targetNode 往后移，扭转 targetNode=targetNode->next[0]，如果大于，则没找到，完结。因为这曾经是第 0 级，没法再降了。

思考到频繁呈现的 term，如 gender 里的男或女。如有 1 百万个文档，那性别为男的 posting list 里就会有 50 万个 int 值。用 FOR 编码进行压缩可极大缩小磁盘占用, 对于缩小索引尺寸有十分重要的意义。当然 MySql B- 树里也有相似的 posting list，是未经这样压缩的。因为 FOR 的编码有解压缩老本, 利用 skip list，除了跳过了遍历的老本，也跳过理解压缩这些压缩过的 block 的过程，从而节俭了 CPU。

Frame Of Reference

以下三个步骤组成了 Frame Of Reference(FOR)压缩编码技术

Step 1：增量编码

Step 2：宰割成块

Lucene 每个块是 256 个文档 ID，每个块增量编码后每个元素都不会超过 256(1 byte). 为不便演示，图中假如每个块是 3 个文档 ID。

Step 3：按需分配空间

对于第一个块 [73, 227, 2]，最大元素是 227，须要 8 bits，那给这个块的每个元素，都调配 8 bits 的空间。但对于第二个块[30,11,29]，最大才 30，只需 5bits，那给每个元素只调配 5bits 空间。这一步可说是精打细算，按需分配。

2) 利用 bitset 合并

Bitset 是一种很直观的数据结构，posting list 如:[1,3,4,7,10]对应的 bitset 就是:[1,0,1,1,0,0,1,0,0,1], 每个文档依照文档 id 排序对应其中的一个 bit。Bitset 本身就有压缩的特点，其用一个 byte 就能够代表 8 个文档。所以 100 万个文档只须要 12.5 万个 byte。但思考到文档可能有数十亿之多，在内存里保留 bitset 依然是很侈靡的事件。且对于每一个 filter 都要耗费一个 bitset，比方 age=18 缓存起来的话是一个 bitset，18<=age<25 是另外一个 filter, 缓存起来也要一个 bitset。所以须要一个数据结构：

• 能够压缩地保留上亿个 bit 代表对应的文档是否匹配 filter；
• 压缩的 bitset 依然能够很快地进行 AND 和 OR 的逻辑操作。

Roaring Bitmap

Lucene 应用这个数据结构，其压缩思路其实很简略, 与其保留 100 个 0，占用 100 个 bit，还不如保留 0 一次，而后申明这个 0 反复了 100 遍。

bitmap 不论有多少文档，占用的空间都一样。譬如一个数组外面只有两个文档 ID：[0, 65535]，示意[1,0,0,0,….(很多个 0),…,0,0,1]，须要 65536 个 bit，也就是 65536/8=8192 bytes。而用 Integer 数组只需 2 *2bytes=4 bytes。可见在文档数量不多时应用 Integer 数组更节俭内存。算一下临界值，无论文档数量多少，bitmap 都须要 8192bytes，而 Integer 数组则和文档数量成线性相关，每个文档 ID 占 2bytes，所以 8192/2=4096，当文档数量少于 4096 时用 Integer 数组，否则用 bitmap.

1. 存储文档的缩小形式

一种常见的压缩存储工夫序列的形式是把多个数据点合并成一行。Opentsdb 反对海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫 compaction。相似的 vivdcortext 应用 MySql 存储的时候，也把一分钟的很多数据点合并存储到 MySql 的一行以缩小行数。

ES 可实现相似优化，那就是 Nested Document。可把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档。这样可把数据点公共的维度字段上移到父文档里，而不必在每个子文档里反复存储，从而缩小索引的尺寸。

存储时，无论父文档还是子文档，对于 Lucene 来说都是文档，都会有文档 Id。但对于嵌套文档来说，能够保留起子文档和父文档的文档 id 是间断的，且父文档总是最初一个。有这样一个排序性作为保障，那么有一个所有父文档的 posting list 就可跟踪所有的父子关系。也能够很容易地在父子文档 id 之间做转换。把父子关系也了解为一个 filter，那么查问检索的时候不过是又 AND 了另外一个 filter 而已。

应用了嵌套文档之后，对于 term 的 posting list 只须要保留父文档的 docid 就可，能够比保留所有的数据点的 doc id 要少很多。如可在一个父文档里塞入 50 个嵌套文档，那 posting list 可变成之前的 1 /50。

… … …

六．对象与块存储

本章节形容，以 Ceph 分布式存储系统为参考。

1. 对象存储构造

在文件系统一级提供服务，只是优化了目前的文件系统，采纳扁平化形式，弃用了目录树结构，便于共享，高速拜访。

对象存储体系结构定义了一个新的、更加智能化的磁盘接口 OSD。OSD 是与网络连接的设施，蕴含存储介质，如磁盘或磁带，并具备足够智能可治理本地存储的数据。计算结点间接与 OSD 通信，拜访它存储的数据，不须要文件服务器的染指。对象存储构造提供的性能是目前其它存储构造难以达到的，如 ActiveScale 对象存储文件系统的带宽能够达到 10GB/s。

对象存储的构造包含元数据服务器（管制节点 MDS）和数据存储服务器（OSD），两者进行数据的存储，还需客服端进行存储的服务拜访和应用。

2. 块设施存储

块存储技术的构成基础是最上层的硬件存储设备，可能是机械硬盘也可能是固态硬盘。一个操作系统下能够独立管制多个硬件存储设备，但这些硬件存储设备的工作绝对独立，通过操作系统命令看到的也是几个独立的设施文件。通过阵列管制层的设施能够在同一个操作系统下协同管制多个存储设备，让后者在操作系统层被视为同一个存储设备。

典型设施：磁盘阵列，硬盘，虚构硬盘，这种接口通常以 QEMU Driver 或者 Kernel Module 的形式存在，接口须要实现 Linux 的 Block Device 的接口或者 QEMU 提供的 Block Driver 接口，如 Sheepdog，AWS 的 EBS，阿里云的盘古零碎，还有 Ceph 的 RBD（RBD 是 Ceph 面向块存储的接口）。

• 可通过 Raid 与 LVM 等伎俩对数据提供了爱护;
• 多块便宜的硬盘组合起来，进步容量;
• 多块磁盘组合进去的逻辑盘，晋升读写效率。

Ceph 的 RBD(RADOS Block Device)应用形式：先创立一个块设施，而后映射块设施到服务器，挂载后即可应用。

七．矩阵的存储构造

阐明：本章节以矩阵存储为重心，而非矩阵的运算。

矩阵具备元素数目固定以及元素按下标关系有序排列等特点，所以在应用高级语言编程时，个别是用二维数组来存储矩阵。数据库表数据是行列存储，可视为矩阵的利用模式。矩阵的存储包含齐全存储和稠密存储形式。

1. 惯例 & 非凡矩阵状态

惯例矩阵状态

采纳二维数组来存储，可按行优先或列优先的模式记录。

非凡矩阵状态

非凡矩阵指的是具备许多雷同元素或零元素，并且这些元素的散布有肯定规律性的矩阵。这种矩阵如果还应用惯例形式来存储，就会产生大量的空间节约，为了节俭存储空间，能够对这类矩阵采纳压缩存储，压缩存储的形式是把那些出现规律性散布的雷同元素只调配一个存储空间，对零元素不调配存储空间。

1) 对称矩阵

对于矩阵中的任何一个元素都有 aij=aji 1≤i,j≤n 这样的矩阵就叫对称矩阵。也就是上三角等于下三角。对于对称矩阵的存储形式是存储上三角或者下三角加对角线，假如一个 n 阶对称方阵，如果全副存储应用的存储空间是 n n，压缩存储则是 n(n+1)/2，对角线元素为 n 个，除了对角线之外为 n n-n，须要存储的元素 (n*n-n)/2，加上对角线上的元素后后果就是 n(n+1)/2。假如存储一个 n 阶对称矩阵，应用 sa[n(n+1)/2] 来存储，那么 sa[k]与 ai,j 的关系是：

当 i >= j 时，k= i(i-1)/2+j-1

当 i <j 时，k =j(j-1)/2+i-1

2) 三角矩阵

上三角或下三角全为雷同元素的矩阵。可用相似于对称矩阵的形式存储，再加上一个地位用来存储上三角或者下三角元素就好。

ai=a0 + (i (i+1) /2+j) size;

size 为每个数据所占用的存储单元大小。

3) 带状对角矩阵

矩阵中所有非 0 元素集中在主对角线为核心的区域中。下图为 3 条对角线区域，其余区域的元素都为 0。除了第一行和最初一行仅 2 个非零元素，其余行都是 3 个非零元素，所以所需的一维空间大小为：3n – 2；

ai 的内存地址 =a00 首地址 + ((3 i -1) + (j-i+1)) size；(size 为每个数据所占用的存储单元大小)。比方首地址为 1000，每个数据占用 2 个存储单元，那么 a45 在内存中的地址 =1000+13 * 2=1026；

1. 稠密矩阵及压缩

因为非凡矩阵中非零元素的散布是有法则的，所以总是能够找到矩阵元素与一维数组下标的对应关系，但还有一种矩阵，矩阵中大多数元素都为 0，个别状况下非零元素个数只占矩阵元素总数的 5% 以下，且元素的散布无规律，这样的矩阵称为稠密矩阵。

三元组程序法

如果采纳惯例办法存储稠密矩阵，会相当节约存储空间，因而只存储非零元素。除了存储非零元素的值之外，还须要同时存储非零元素的行、列地位，也就是三元组(i,j,aij)。矩阵元素的存储程序并没有扭转，也是按列的程序进行存储。

三元组也就是一个矩阵，一个二维数组，每一行三个列，别离为行号、列号、元素值。因为三元组在稠密矩阵与内存地址间表演了一个中间人的角色，所以稠密矩阵进行压缩存储后，便失去了随机存取的个性。

行逻辑链接的程序表

为了随机拜访任意一行的非零元，这种形式须要一个数组指向每一行开始元素 (非零元素) 的地位。这种形式适宜矩阵相乘。

十字链表法

当矩阵中元素非零元个数和地位在操作过程中变动较大时，就不宜采纳顺序存储构造来示意三元组的线性表。如在进行加减操作时，会呈现非零元变成零元的状况，因而，就适宜用十字链表来存储。

十字链表的构造有五个域，一个数据域寄存矩阵元，i、j 域别离寄存该非零元所在的行、列。还有 right、down 域，right 指向左边第一个矩阵元的地位，down 用来指向上面第一个矩阵元的地位。而后建设两个数组，别离指向每行 / 列的第一个元素。十字链表在图中也有利用，用来存储图。

八．图构造存储

图通常用来示意和存储具备“多对多”关系的数据，是数据结构中十分重要的一种构造。

1. 邻接矩阵构造

图的邻接矩阵存储形式是用两个数组来示意图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

设图 G 有 n 个顶点，则邻接矩阵是一个 n * n 的方阵，定义为：

无向图

1）基于邻接矩阵容易判断任意两顶点是否有边无际；

2）某个顶点的度就是这个顶点 vi 在邻接矩阵中第 i 行或 (第 i 列) 的元素和；

3）vi 的所有邻接点就是矩阵中第 i 行元素，如 arci 为 1 就是邻接点；

n 个顶点和 e 条边的无向网图的创立，工夫复杂度为 O(n + n2 + e)，其中对邻接矩阵的初始化消耗了 O(n2)的工夫。

有向图

有向图考究入度和出度，顶点 vi 的入度为 1，正好是第 i 列各数之和。顶点 vi 的出度为 2，即第 i 行的各数之和。

若图 G 是网图，有 n 个顶点，则邻接矩阵是一个 n * n 的方阵，定义为：

wij 示意 (vi,vj) 上的权值。无穷大示意一个计算机容许的、大于所有边上权值的值，也就是一个不可能的极限值。

上面左图是一个有向网图，右图是其邻接矩阵。

2. 邻接表构造

邻接矩阵是不错的一种图存储构造，但对边数绝对顶点较少的图存在对存储空间的极大节约。因而，找到一种数组与链表相结合的存储办法称为邻接表。邻接表的解决办法：

1）图中顶点用一个一维数组存储，当然，顶点也可用单链表来存储，不过数组较容易的读取顶点的信息。

2）图中每个顶点 vi 的所有邻接点形成一个线性表，因为邻接点的个数不定，所以用单链表存储，无向图称为顶点 vi 的边表，有向图则称为顶点 vi 作为弧尾的出边表。

例如，下图就是一个无向图的邻接表的构造。

从图中能够看出，顶点表的各个结点由 data 和 firstedge 两个域示意，data 是数据域，存储顶点的信息，firstedge 是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由 adjvex 和 next 两个域组成。adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标，next 则存储指向边表中下一个结点的指针。

对于带权值的网图，能够在边表结点定义中再减少一个 weight 的数据域，存储权值信息即可，如下图所示。

对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对 i 和 j 散布进行插入。本算法的工夫复杂度，对于 n 个顶点 e 条边来说，容易得出是 O(n+e)。

1. 十字链表存储

对于有向图来说，邻接表是有缺点的。关怀了出度问题，想理解入度就必须要遍历整个图才晓得，反之，逆邻接表解决了入度却不理解出度状况。而十字链表存储办法可把邻接表和逆邻接表联合。

从新定义顶点表结点构造，如下所示

其中 firstin 示意入边表头指针，指向该顶点的入边表中第一个结点，firstout 示意出边表头指针，指向该顶点的出边表中的第一个结点。

从新定义边表构造，如下所示

其中 tailvex 是指弧终点在顶点表的下表，headvex 是指弧起点在顶点表的下标，headlink 是指入边表指针域，指向起点雷同的下一条边，taillink 是指边表指针域，指向终点雷同的下一条边。还可减少一个 weight 域来存储权值。

比方下图，顶点仍然是存入一个一维数组，实线箭头指针的图示齐全与邻接表雷同。就以顶点 v0 来说，firstout 指向的是出边表中的第一个结点 v3。所以 v0 边表结点 hearvex=3，而 tailvex 其实就是以后顶点 v0 的下标 0，因为 v0 只有一个出边顶点，所有 headlink 和 taillink 都是空的。

虚线箭头的含意。它其实就是此图的逆邻接表的示意。对于 v0 来说，它有两个顶点 v1 和 v2 的入边。因而它的 firstin 指向顶点 v1 的边表结点中 headvex 为 0 的结点，如上图圆圈 1。接着由入边结点的 headlink 指向下一个入边顶点 v2，如上图圆圈 2。对于顶点 v1，它有一个入边顶点 v2，所以它的 firstin 指向顶点 v2 的边表结点中 headvex 为 1 的结点，如上图圆圈 3。

十字链表的益处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以 v 为尾的弧，也容易找到以 v 为头的弧，因此较易求得顶点的出度和入度。除了结构复杂一点外，其实创立图算法的工夫复杂度和邻接表雷同，因而在有向图利用中，十字链表是十分好的数据结构模型。

九．分布式图存储

分布式图 (巨型图) 的存储总体上有边宰割和点宰割两种形式，目前业界宽泛承受并应用的存储形式为点宰割，点宰割在解决性能上要高于边宰割。

• 边宰割（Edge-Cut）：每个顶点都存储一次，但有的边会被打断分到两台机器上。这样做的益处是节俭存储空间；害处是对图进行基于边的计算时，对于一条两个顶点被分到不同机器上的边来说，要跨机器通信传输数据，内网通信流量大。
• 点宰割（Vertex-Cut）：每条边只存储一次，都只会呈现在一台机器上。街坊多的点会被复制到多台机器上，减少了存储开销，同时会引发数据同步问题。益处是能够大幅缩小内网通信量。

尽管两种办法互有利弊，但当初是点宰割占上风，各种分布式图计算框架都将本人底层的存储模式变成了点宰割。次要起因有以下两个。

1) 磁盘价格下降，存储空间不再是问题，而内网通信资源无突破性停顿，集群计算时内网带宽是贵重的，工夫比磁盘更宝贵。这点相似于常见的空间换工夫的策略。

2) 在以后利用场景中，绝大多数网络都是“无尺度网络”，遵循幂律散布，不同点的街坊数量相差十分迥异。而边宰割会使那些多街坊的点所相连的边大多数被分到不同的机器上，这样的数据分布会使得内网带宽更加顾此失彼，于是边宰割存储形式被慢慢摈弃。

1. GraphX 存储模式

借鉴 PowerGraph, 应用点宰割形式存储图, 用三个 RDD(Resilient Distributed Dataset, 弹性分布式数据集)存储图数据信息：

VertexTable(id, data): id 为 Vertex id，data 为 Edge data

EdgeTable(pid, src, dst, data):pid 为 PartionId，src 为原顶点 id，dst 为目标顶点 id

RoutingTable(id, pid)：id 为 Vertex id，pid 为 Partion id

点宰割存储实现如下图所示：

1. 超大规模图存储

超大规模图（数十亿点，数百亿边）存储，须要分布式的存储架构。在图加载时，整张图在图解决引擎外部被切分为多个子图，每个计算节点被调配 1 个或几个子图进行加载。

一张有向图的根本元素是顶点和边, 个别都具备类型和权重，边是有向的，一条边由：终点、起点、类型三者标识，即雷同的两点之间能够同时具备多条不同类型的边。上面是一个简略的带权异构属性图示例：

顶点以 uint64 标识，顶点类型、边类型，以及点边上的三种属性均采纳字符串形容。对于例子中的图，须要将点边归类编号，失去一张能够辨认的图。

图数据 JSON 格局

JSON 文件由两大部分组成，点和边，别离存储在 JSON 对象的“nodes”、“edges”中。每个节点对象蕴含了节点的 id，type，weight 以及 name，type 和 value 属性信息字段。每个边对象则蕴含这个边相关联的终点和起点 id：src 和 dst，和边相干的属性信息。

点和边属性索引

• 全局 hash 索引：全局采样过滤准确匹配某种属性的点和边。实用于全局采样负例的时候，加上过滤条件，只采样满足条件的负例。反对的查问有：eq，not_eq，in，not_in。
• 全局 range 索引：全局采样过滤某种属性在某个范畴内的点和边。实用于全局采样负例时，加上过滤条件采样满足条件的负例。反对：eq，not_eq，ge，le，gt，lt，in，not_in
• 街坊索引：采样某个点的满足某种属性的街坊节点。实用于街坊采样的时候，加上过滤条件，只采样满足条件的街坊节点。反对的查问与全局 range 索引雷同。

图数据二进制生成

将 JSON 文件转化为分布式图引擎加载所须要的二进制格局，包含分片个数等。

… 广告搜寻场景：图嵌入，向量化最近邻检索网络结构

… …

最 后

当今的计算机以运算器为核心，I/ O 设施与存储器间的数据传送都要通过运算器。绝对处理器的速度来说，IO 设施就慢多了。就 SSD 来说，IO 也是远低于 RAM 的读写速率。IO 读写的耗时经常成为性能的瓶颈点，所以要缩小 IO 次数，且随着数据量减少，IO 次数稳固是数据存储引擎的外围要务。当然了，CPU 等指标也是很重要的。

文中倒排索引存储章节介绍了 Lucene 如何实现倒排索引的关键技术，如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算放慢处理速度，但往高处思考，再类比一下 MySql 就会发现，尽管都是索引，但实现机制却截然不同。

很多业务、技术上要解决的问题，大都能够形象为一道算法题，简单问题简单化。每种数据存储引擎都有本人要解决的问题（或者说善于的畛域），对应的就有本人的数据结构，而不同的应用场景和数据结构，须要引入不同的索引，能力起到最大化放慢查问、检索的目标。

… ……

**[点击关注，第一工夫理解华为云陈腐技术~](https://bbs.huaweicloud.com/b…
)**