摘要：常见存储算法构造涵盖：哈希存储，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阶对称方阵，如果全副存储应用的存储空间是nn，压缩存储则是n(n+1)/2，对角线元素为n个，除了对角线之外为nn-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...
)**