慢慢的博客

图数据库

 Posts  2221  5 分钟

简介

图数据库（Graph Database）是基于图论实现的一种新型 NoSQL 数据库。他的数据存储结构和数据的查询方式都是以图论为基础的。图论中图的基本元素为节点和边，在图数据库中对应的就是节点和关系。

在图数据库中，数据与数据之间的关系通过节点和关系构成一个图结构并在此结构上实现数据库的所有特性：对图数据对象进行创建、读取、更新、删除等操作，还有处理事务的能力和高可用性。

随着社交、电商、金融、零售、物联网等行业的快速发展，现实社会织起了了一张庞大而复杂的关系网，传统数据库很难处理关系运算。图数据库也随之应运而生。

图数据库有很多的使用场景：

  • 社交领域：Facebook, Twitter，Linkedin 用它来管理社交关系，实现好友推荐；
  • 零售领域 ：eBay，沃尔玛使用它实现商品实时推荐，给买家更好的购物体验；
  • 金融领域 ：摩根大通，花旗和瑞银等银行在用图数据库做风控处理；
  • 电信领域 ：Verizon, Orange 和 AT&T 等电信公司依靠图数据库来管理网络，控制访问并支持客户 360；

Neo4j

Neo4j 是由 java 实现的开源 NoSQL 图书库。Neo4j 实现了专业数据库级别的图数据库模型的存储。

Neo4j 最初的设计动机是为了更好地描述实体之间地联系。现实生活中，每个实体都与周围地其他实体有着千丝万缕的关系，这些关系里存在着大量的潜在信息。但是传统关系型数据库更加注重刻画实体内部的属性，实体与实体之间的关系主要通过外键来实现。因此，在查询一个实体的关系时需要 join 操作，特别时深层次的关系查询需要大量的 join 操作，而 join 操作通常又非常耗时。随着现实世界中关系数据的急剧增加，导致关系型数据库已经主键地难以承载查询海量数据的深层次关系的操作。

1. Neo4j 的数据类型

Neo4j 有两种数据类型：

  • 节点：节点类似于 E-R 图中的实体，每一个实体可以有零个或多个属性，这些属性以 key-value 的形式存在。属性没有特殊的类型要求，同时每个节点还具有相应的标签，用来区分不同类型的节点；
  • 关系：关系也类似于 E-R 图中的边，一个关系有起始节点和终止节点（即边上连接的两个点），与节点一样，关系也能够有自己的属性和标签（指明这个是什么关系：朋友、亲戚等）

节点和关系分别采用固定长度存储，每个节点记录的长度为 9 字节，格式为：Node:inUse+nextRelId+nextProId

  • inUse：1 表示该节点被正常使用，0 表示该节点被删除
  • nextRelId：该节点的下一个关系 ID
  • nextPropId：该节点的下一个属性 ID，属性 Id 通过链表的形式来关联，即有查询该节点下的所有属性，需要通过遍历下一指针的方式找出所有的属性。

每个关系记录的长度为 33 字节，格式为： Relationship:inUse+firstNode+secondNode+relType+firstPrevRelId+firstNextRelId+secondPrevRelId+secondNextRelId+nextPropId

  • inUse：1 表示该节点被正常使用，0 表示该节点被删除
  • nextPropId：该节点的下一个属性 ID
  • relType：关系的类型
  • firstNode、secondNode：这个关系关联的两个节点，为起始节点和终止节点
  • firstPrevRelId、firstNextRelId：起始节点的前一个和后一个关系的 ID
  • secondPrevRelId、secondNextRelId：终止节点的前一个和后一个关系的 ID

2. Neo4j 遍历方式

每个节点记录都包含一个指向该节点的第一个属性的指针和关系链中的第一个关系的指针。要读取一个节点的属性，从指向第一个属性的指针开始，遍历整个单向链表；要找到一个节点的关系，从指向的第一个关系开始，遍历整个双向链表，直到找到了感兴趣的关系

下面通过一个例子来说明 Neo4j 遍历关系和节点的详细过程。加入在 Neo4j 中存储了 A、B、C、D、E 5 个节点和 R1、R2、R3、R4、R5、R6、R7，7 个关系，它们之间的关系如下：

假如遍历图中节点 B 的所有关系，只需要向 NODEB-NEXT 方向遍历，直到指向 NULL 为止，可以从下图中看出节点 B 的所有关系为 R1、R2、R3、R4、R5。

通过固定大小的存储记录和指针 ID，只要跟随指针就可以简单地实现遍历并且高速执行。要遍历一个节点到另一个节点的特定关系，在 Neo4j 中只需遍历几个指针，然后执行一些低成本的 ID 计算即可，这相较于全局索引的时间复杂度要低很多，这就是 Neo4j 实现高速遍历的秘密。

  • 从一个给定节点定位关系链中第一个关系的位置，可以通过计算它在关系存储的偏移量来获得。跟获得节点存储位置的方法一样，使用关系 ID 乘以关系记录的固定大小即可找到关系在存储文件中的正确位置
  • 在关系记录中，搜索第二个字段可以找到第二个节点的 ID，用节点记录大小乘以节点 ID 可以得到节点在存储中的正确位置。

3. Neo4j 的存储优化

Neo4j 支持存储优化（压缩和内联存储属性值），对于某些短字符的属性可以直接存储在属性文件中。在实际操作中，像邮政编码、电话号码这样的短字符串属性就可以直接内联到属性存储文件，而不是单独地放在另一个动态存储区，这就大幅减少 I/O 操作并且增大吞吐量，因为只有一个文件需要访问。

除了内联属性值，Neo4j 还可以对属性名称地空间严格维护，例如在社交网络中，有可能会有多个节点存在 first_name 和 last_name 这样的属性，如果将每个属性都逐字写入磁盘上就会造成存储浪费。因此，替代方案是属性名通过属性索引文件从属性存储中间接引用。属性索引允许所有具有相同名称的属性共享单个记录。

即使现在的磁盘访问速度已经很快了，但是 CPU 访问磁盘仍然比 CPU 直接访问高速缓存要慢得多。因此，Neo4j 采用了缓存策略，保证那些经常访问的数据可以快速地被多次重复访问。Neo4j 高速缓存地页面置换算法是基于最不经常使用地页置换（LFU）。

参考：

updatedupdated2022-06-232022-06-23

相关文章：