相关研究工作: R树结构




与B树相似，R树是一种高度平衡的树，它的叶 子节点的记录包含数据对象的指针。 如果索引是磁盘驻留的，则每个节点对应一个 磁盘页，以节点为单位读取和写入。 该结构设计使得空间搜索只需要访问一小部分 的节点，大大提高检索效率。 索引结构是完全动态的；插入、删除和查找操 作能同时进行而且不需要定期地对树的结构进 行重新组织
物联网数据存储现状分析



从而使得一些复杂查询非常耗时、效率 低下， 不能有效地支持用户或管理者查找到想 要的文件，或得到想要的数据。 例如，“我最近修改过的PPT在哪？” 或者“我的目录下这个文件有几个副本？
物联网数据存储现状分析



为了解决上述问题，必须提供一种高效的多维 元数据查询系统，而且必须满足以下特点： 第一，必须能够从存储系统中快速收集到元数 据； 第二，查询和更新必须快速而且可扩展； 第三，必须能够快速的返回计算结果，比如用 户提交一个复杂查询后并不想长时间在线等待 计算结果，有时这个过程非常费时
B树
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[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）
海量元数据查询需求分析



易用的查询接口 大多数系统输出简单的查询应用程序接 口， 但是研究表明专门设计的接口能够很好 表达且容易使用， 这会大大提升查询体验。
物联网元数据管理系统设计


系统设计要求 第一、高性能，能够快速的从文件系统中聚集 元数据，解决并发操作、热点数据的管理和访 问等问题； 第二、查找和更新速度必须快且可靠。现有的 系统一般采用通用的DBMS来索引元数据，但 是通用的DBMS的设计并不完全适合各种应用 场合，比如元数据查找，特别是支持各种复杂 的元数据查询，热点数据查询等；而且在大规 模存储系统中会限制其性能和扩展性。
物联网数据存储现状分析


这与互联网环境形成了鲜明的对比： 由于搜索引擎技术的发展，在互联网的 环境下查找信息很方便， 而用户在存储系统中找到想要的信息比 在互联网上查找信息更加困难
物联网数据存储现状分析



如今存储系统中的数据量的快速增长使 得查找和管理文件异常的困难， 为了能够合理的管理这些不断增多的海 量数据， 不管是用户还是管理者都需要能够高效 的获得文件的属性。
相关研究工作: R树结构
海量元数据查询需求分析



在大规模存储系统提供高效的元数据查 询是一个很大的挑战， 而现在有一些商业元数据查询系统主要 致力于小型的存储系统（最多几千万个 文件） 并且常常很慢，耗费的资源多
海量元数据查询需求分析



ቤተ መጻሕፍቲ ባይዱ
在大规模存储系统中想要实现高效的元数据 查询，需满足以下几点: 最小的资源需求 元数据查询不应该需要额外的硬件，它应该 集成到存储系统中而不降低系统的性能。 现在大多数的元数据查询系统都需要专门的 CPU、内存以及磁盘， 使得它们非常昂贵而且很难部署，这就限制 它们的扩展性
物联网数据存储现状分析



元数据查询包含索引文件元数据，例如 索引节点和一些扩展属性，能够帮助回 答很多复杂查询问题。 利用文件属性，元数据查询允许点查询、 范围查询、top-k查询和聚集查询， 这些使得复杂的、特定的查询变得简单。
物联网数据存储现状分析



能够帮助管理者回答 “哪些文件在过去的一周里增长很快？” 或者是“哪些应用程序和用户的文件占用大多 数存储空间？” 元数据查询也能够帮助用户找到10个最近访问 的报告或最大的虚拟机镜像。 准确地回答这些问题能够极大的提高用户和管 理者管理大规模存储系统中的文件。
多维元数据组织结构



如果系统基于每个维度单独建立索引，则需要 对每个维度进行查找之后将结果做交集。 如果系统按照多维属性信息建立了空间索引结 构，则可以同时在文件大小、创建时间和修改 时间这个三个属性维度上做约束，大大减少了 查询的数据量和查询的时间代价。 系统耗费一定的存储空间维护空间索引结构， 在提供各种复杂查询服务时可以有效的减少查 询时间延迟
B树
B+树
B+树是B-树的变体，也是一种多路搜索树： 1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值 属于[K[i], K[i+1])的子树（B-树是开区间）； 5.为所有叶子结点增加一个链指针； 6.所有关键字都在叶子结点出现； 如：（M=3）
物联网数据存储现状分析



在海量的数据中，让用户获得想要的信 息至关重要， 对存储系统中多维元数据查询的研究将 大大提高文件元数据的查询效率， 实现复杂查询，缩短响应时间， 这对于用户或管理者查找和管理文件， 以及决策支持都有重要的意义
海量元数据查询需求分析




现在的存储系统都是采用层次化的目录结构来 组织文件的，层次化结构使得文件的访问效率 不高。 访问某个文件必须通过层次型的目录树结构到 达文件的保存位置， 如果不知道文件保存位置，就必须遍历整个目 录或使用操作系统的搜索功能， 而操作系统仅能依靠文件名来检索和查找数据。
相关研究工作:B树、B-树、 B+树、B*树




B树：二叉树，每个结点只存储一个关键字，等于 则命中，小于走左结点，大于走右结点； B-树：多路搜索树，每个结点存储M/2到M个关键 字，非叶子结点存储指向关键字范围的子结点； 所有关键字在整颗树中出现，且只出现一次，非 叶子结点可以命中； B+树：在B-树基础上，为叶子结点增加链表指针， 所有关键字都在叶子结点中出现，非叶子结点作为叶 子结点的索引；B+树总是到叶子结点才命中； B*树：在B+树基础上，为非叶子结点也增加链表 指针，将结点的最低利用率从1/2提高到2/3；



传统的索引方法已不能满足多维数据的 索引和查询要求， 比如哈希表是数据的精确匹配而不能进 行范围查询， 而B树索引一维数据而不能搜索多维空间。 目前存在大量的空间数据索引方法
多维元数据组织结构




一般来说，常见的多维空间数据索引有两种数 据组织方式：基于规则的分割方法和基于数据 的分割方法。 基于规则分割的索引结构按照特定算法对数据 空间进行划分，包括KD树、网格等， 这种方法仅适用于数据分布均匀的情况，在数 据分布不均匀时会引起索引结构的不平衡。 基于数据的分割方法有R树，Cell树等，按照数 据的分布特性逐层划分空间
物联网数据存储现状分析



例如 “某公司想统计一个星期内用户产生的 数据总量有多少？” 或者“最近一星期内排前五名的热点文 件是哪五个？”， 用户或管理者希望系统能够预先计算好 这些结果而不用在线等待，当提交查询 后能够快速返回结果
物联网数据存储现状分析


第四，资源需求必须很低，现存的很多 元数据查询工具需要专门的CPU、内存以 及硬盘，这就使得它们非常昂贵而且很 难集成到存储系统中； 第五，查询的接口必须灵活好用，对于 现存的文件系统接口和查询语言，复杂 查询非常困难
目录

物联网数据存储现状分析 海量元数据查询需求分析 物联网元数据管理系统设计 面向数据更新的结构设计和分析 面向预计算的元数据组织结构－数据立 方体
物联网数据存储现状分析


大规模存储系统的应用越来越广泛，存 储容量也从以前的TB（Terabyte）级上 升到PB（Petabyte）级甚至EB（Exabyte） 级。 随着存储系统规模不断增大，在大规模 文件系统中，文件的数量高达几十亿个， 在这种海量数据中查找和管理文件变得 异常困难。
海量元数据查询需求分析



快速的元数据收集 必须从几十亿、几百亿个文件中周期性 的收集发生改变的元数据， 而不会给整个存储系统带来额外负载， 使得系统变慢。 现在的爬行算法（crawling method） 非常慢而且消耗系统资源
海量元数据查询需求分析



快速可扩展的索引查询和更新 查询必须快速，甚至随着系统规模的扩 大，性能依旧能保持很好，能够快速周 期性的对元数据索引进行更新。 但是，现存的系统一般都采用通用型的 关系型数据库来索引元数据。 DBMS常常使用重量级的锁和事务，这 给系统增加负载
B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针； B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用 率为2/3（代替B+树的1/2）； B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中 1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树 的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要 指向兄弟的指针；
相关研究工作:B树、B-树、 B+树、B*树

B树 即二叉搜索树： 1.所有非叶子结点至多拥有两个儿子（Left和Right）； 2.所有结点存储一个关键字； 3.非叶子结点的左指针指向小 于其关键字的子树，右指针 指向大于其关键字的子树； 如：