万字长文带你详解九大数据存储引擎结构（上）

介绍

在存储系统的设计中，存储引擎属于底层数据结构，直接决定了存储系统所能够提供的性能和功能。常见存储算法结构涵盖：哈希存储，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.  常用哈希函数

构造哈希函数的总的原则是尽可能将关键字集合空间均匀的映射到地址集合空间中，同时尽可能降低冲突发生的概率。

l  除留余数法:H(Key)=key % p (p ≤ m)p最好选择一个小于或等于m(哈希地址集合的个数)的某个最大素数。

l  直接地址法: H(Key) =a * Key + b；“a，b”是常量。

l  数字分析法

比如有一组key1=112233，key2=112633，key3=119033，分析数中间两个数比较波动，其他数不变。那么取key的值就可以是 key1=22,key2=26,key3=90。

l  平方取中法

l  折叠法

比如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,目的就是高性能、高可用、易扩展。

2.  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)

http://image.huawei.cn/tiny-lts/v1/images/ab7fb27100c2713ef8fe_803x467.jpg@900-0-90-f.jpg

相对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的文件，减少无谓查找；

2.  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中获取。

3.  图库ArangoDB LSM

ArangoDB采用RocksDB做底层存储引擎，RocksDB使用LSM-Tree数据结构.

存储的格式非常类似JSON，叫做VelocyPack格式的二进制格式存储。

• 文档被组织在集合中。
• 有两种集合：文档（V），边集合（E）
• 边集合也是以文档形式存储，但包含两个特殊的属性_from和_to，被用来创建在文档和文档之间创建关系

索引类型

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

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

·       Hash Index，自建

·       Skiplist Index，有序索引，

•  用于快速查找具有特定属性值的文档，范围查询以及按索引排序，顺序返回文档。
• 用于查找，范围查询和排序。补全范围查询的缺点。

·       Persistent Index，RocksDB的索引。

• 持久性索引是具有持久性的排序索引。当存储或更新文档时，索引条目将写入磁盘。
•  使用持久性索引可能会减少集合加载时间。

·      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如美团、大众点评、手淘等都可看到其应用身影。

----------未完，请阅读（下）-------

万字长文带你详解九大数据存储引擎结构（下）