前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >通识 | 数据结构图如何利用大数据框架存

通识 | 数据结构图如何利用大数据框架存

作者头像
Spark学习技巧
发布2019-11-07 15:12:34
7040
发布2019-11-07 15:12:34
举报
文章被收录于专栏:Spark学习技巧

很久没写过文章了,今天就分享一下大数据中的图数据库Janusgraph的存储模型。希望对想做大数据图存储的粉丝有一定的帮助吧。由于没时间画图,所以图片来源于网络和Janusgraph官网,感谢各位作者的贡献。

图的存储结构

什么是图?图基本描述有定点,边,属性三种组成,常见的结构如下:

这奇奇怪怪的网络结构组成的图形就是图。

那么计算机中都是如何存储图的呢?学过数据结构的应该都知道图的基本存储结构有以下几种:

  1. 邻接矩阵
  2. 邻接表
  3. 十字链表
  4. 邻接多重表
  5. 边集数组

至于这几种图的存储模型具体数据结构描述,建议大家可以百度或者去找本数据结构的书看看。

大数据常用的图数据库Janusgraph底层是采用的邻接表的形式存储图的。邻接表的存储结构如下:

  • 图中顶点用一个一维数组存储,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息
  • 图中每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点Vi的边表,有向图则称为顶点Vi作为弧尾的出边表

这种存储结构用大数据的框架去存,大家会不会首先想到hbase?hbase的存储结构就如下图所示:

hbase的表结构就是由 rowkey+列簇,每个列簇有没有限制的列(cell)组成。当然列不可能没有限制,列过大不便于查询,遍历效率低下。

与邻接表对比思考一下,hbase是不是很符合图的存储结构邻接表的表述:

rowkey就是类似于定点数组,一个列簇类似一个链表,存储相邻顶点集。由于一个顶点相邻顶点个数不定,而hbase对列簇里的列数有没有强制的数量限制,就刚刚好表述图的邻接表的存储模型。

下面是一个人际关系的简单的图,图中顶点标签是人,边标签是同事,还有各种属性,比如name,sinceYear。

可以见图存储的对象主要是顶点,边,属性。整理之后应该如下:

顶点存储的时候可以以一定的格式设计存储为rowkey,格式下面贴图,就不细讲了,在Janusgraph里面顶点id就是64bit。然后属性和边都视为一种存储结构,就是对应hbase的cell也即是一个列。属性也可以绑定到固定的边上。然后结构就是下面的样子

边和属性的内部存储结构也基本类似的,如下:

Edge和Property在cell中都是由column(列)和value(值)组成。

Edge中column由labelid(边标签id)+direction(边的方向,相对于节点的出边或者入边)+sort key(用于边排序的key)+adjacent vertex id(临近顶点的id)+edge id(边id)组成,value由signature key(签名密匙)+other properties(边的其他属性)组成。

Property中column由key id(属性的键id)组成,value由属性id+属性值组成。

顶点的结构如下:

这个小文章只是帮助大家对图在jansugraph的存储方式,后续会分析更多jansugraph的知识和经验,欢迎大家关注浪尖微信公众号。

官网地址https://florianhockmann.github.io/docs.janusgraph.org/0.4.0/data-model.html

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 浪尖聊大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档