第 1 章
? Neo4j 图数据库基础 ?

本章包括以下内容：
? 图数据库的产生背景
? 图数据库基础
? 图数据库与关系数据库的对比
? 图数据库与其他NoSQL数据库的对比
? Neo4j概述
? Neo4j体系结构图解
大多数读者，即便是计算机科班出身，如果没有紧跟数据库发展，一听到Neo4j定然会比较陌生，但一般来说肯定会或多或少地接触到那些耳熟能详的传统关系型数据库产品，比如：Oracle、MySQL、SQL Server等。事实上，Neo4j是一种新型的数据库产品，除了能像传统关系型数据库支持存储、分析、处理数据的功能以外，它以数学中的图论为理论根基，更擅长海量数据之间的复杂关系分析，因此，在学术界和产业界通常将它称作：图数据库（Graph Database，广义上属于NoSQL数据库的一种）。对于广大使用者而言，如果不需要深入数据库本身的研发，Neo4j与传统关系型数据库相似，不需要系统学习较为高深的建立在数学集合论基础之上的关系代数，仅需掌握一定的SQL（Structured Query Language，结构化查询语言）知识。同样，使用Neo4j不需要钻研深奥的图论的理论知识，只需了解与SQL语言类似的Cypher语言即可。作为最近几年才发展起来的全新数据库技术，Neo4j紧随大数据时代的步伐不断前行，越发凸显出相对于传统关系型数据库的强大优势，必将成为这个时代一颗璀璨的明珠！本书将带您一起遨游于Neo4j图数据库这一极富迷人魅力的广阔海洋！
本章作为全书的第1章，主要有两个目标：了解图数据库的基础知识和认识Neo4j。首先介绍图数据的基本知识并将图数据库与传统数据库进行对比分析；然后介绍Neo4j图数据库的产生、发展以及其性能优势；最后一节介绍Neo4j的体系结构，这样可以对Neo4j的技术架构有个初步的认识。
本章将只讨论理论、概念性的知识，有了一定的理论基础后就可以在后续章节中更好地学习Neo4j的技术知识。
1.1  图数据库的产生背景
任何一项重大科学技术的产生都有其历史背景和必然规律。同样，作为计算机科学基础软件领域的数据库技术也有其产生和发展的历史必然性。下面简要回顾数据库技术发展历程中具有里程碑意义的事件。
1. 数据库技术发展的里程碑事件
（1）1962年，数据库（Database）一词最早流行于加利福尼亚州（硅谷所在地）一些系统研发公司的技术备忘录中。
（2）1968年，伴随阿波罗登月计划，商业数据库雏形诞生，IBM公司的IMS（Information Management System）、Mainframe，以及Navigational数据库技术出现。
（3）1969年，美国国防部召开的数据系统语言会议（Conference on Data Systems Languages，CODASYL）发布了一份“DBTG（Database Task Group）报告”，标志网状数据库系统进入标准化进程。
（4）1970年，IBM公司研究员Edgar Frank Codd发表了题为“A Relational Model of Data for Large Shared Data Banks”（译为“大型共享数据库的数据关系模型”）的论文，这篇论文提出了关系模型的概念，奠定了关系模型的理论基础，他本人被誉为“关系数据库之父”，并于1981年获得了有“计算机界的诺贝尔奖”之称的“图灵奖”。
（5）1974年，IBM公司的校企联合计划中，与加州大学伯克利分校Ingres数据库研究项目携手创建了RDBMS（Relation DataBase Management System，关系数据库管理系统）System R原型。
（6）1979年，因IBM公司战略调整其为当时主流的层次数据库，并剥离出处于萌芽状态的关系数据库；加州大学伯克利分校Ingres数据库研究项目联合Oracle公司的Larry Ellison创建了第一个商业关系数据库产品。
（7）1983年，IBM公司发布其第一款自主研发的关系数据库产品DB2。
（8）1984年，天睿公司（Terodata Corporation）发布第一个MPP（Massive Parallel Processor，大规模并行处理）分布式数据库专用平台，或称为无共享架构（Sharing Nothing Architecture），有效提升了系统整体性能。
（9）1986年，首款面向对象数据库GemStone/S出现。
（10）1988年，IBM公司研究员率先提出数据仓库（Data Warehouse），主要用于复杂数据分析，并制定相关行业标准，将数据处理分为两大块业务：联机事务处理（On-Line Transaction Processing，OLTP）和联机分析处理（On-Line Analytical Processing，OLAP）。
（11）1995年，瑞典MySQL AB公司发布第一款开源关系数据库MySQL。
（12）1996年，第一款对象关系数据库Illustra问世，支持高效的对象和关系数据存储与管理。
（13）1998年，随着互联网的兴起，Lawrence Edward Page和Sergey Brin在斯坦福大学宿舍内共同开发了谷歌在线搜索引擎。
（14）1998年，James Gray因在数据库和事务处理方面的突出贡献而获1998年的图灵奖。
（15）2003年，MarkLogic公司发布第一款NoSQL（Not Only SQL，泛指非关系型的数据库）数据库解决方案，XML数据库。
（16）2005年，受Google公司的 Map/Reduce 和 Google File System（GFS）的启发，由Apache基金会所开发的分布式系统基础架构Hadoop发布。
（17）2005年，针对普遍存在的流数据，Streambase公司发布第一款支持流数据处理的复杂事件处理（Complex Event Processing，CEP）解决方案。
（18）2007年，Neo4j公司推出第一款商用NoSQL图数据库，高效支持数据之间的复杂关系分析。
（19）2009年，分布式文件存储的数据库MongoDB发布，为Web应用提供可扩展的高性能数据存储解决方案。
（20）2010年，HBase发行，采用列式存储而非行式，在Hadoop之上提供类似Bigtable能力，支持非结构化数据存储。
（21）2013年，有媒体将2013年称为“大数据元年”，“数据即资源”受到广泛认可。
（22）2014年，Michael Stonebraker因对现代数据库的概念和实践作出的根本性贡献获得2014年图灵奖。
（23）2015年，大数据、云计算技术得到广大企业和各国政府的青睐，技术和平台上突飞猛进，比如VoltDB、Spark、Drill等，单是Apache基金会就发布超过25个数据工程项目。
2. 数据的4V
不难发现，数据库技术已经有50多年的历史，在计算机领域中算得上是一直保持蓬勃生机与活力的技术之一。其主要表现在如下几个方面。
（1）数据种类多样化。数据从最初的结构化数据（如数字、符号等信息）拓展为半结构化数据（如HTML文档等），再到非结构化数据（如办公文档、文本、图片、XML、各类报表、图像和音视频信息等）。IDC（国际数据公司）的调查报告显示：企业80%的数据都是非结构化数据，且每年按指数增长60%。
（2）数据量增长迅猛。根据IDC的监测统计，2011年全球数据总量已经达到1.8 ZB（270字节），而这个数值还在以每2年翻一番的速度增长，预计到2020年，全球将总共拥有35 ZB的数据量，比2011年增长近20倍。也就是说，近2年产生的数据总量相当于人类有史以来所有数据量的总和。
（3）数据产生速度快。受摩尔定律的支配，计算机硬件及网络速度每18个月增加一倍，显然导致数据产生的速度飞速提升。
（4）数据价值备受关注。数据价值由先前的少量局部数据内的价值转向大量全局数据之间的价值，不断涌现出数据仓库、数据挖掘、分布式数据分析等技术。
上述4个方面，无不集中展现到当前所处的大数据时代这一历史舞台中，凸显出数据的4V（Volume大量、Velocity高速、Variety多样、Value价值）特性。从上述数据库的简要发展历程稍作分析，便不难发现：数据信息化进程和对数据价值的不断渴求可以说是持续支撑数据库技术发展的不竭动力源泉。
3. 关系型数据库（SQL类）和非关系型数据库（NoSQL类）
在这精彩纷呈的数据库技术发展历程中，是否存在一种“包打天下的武学秘籍，包治百病的旷世神方”呢？它能有效解决上述所有难题，作为数据库领域霸主的关系型数据库行吗？或许这个问题似乎难以回答。将数据库技术发展历程中的主要技术稍加归类整理，可绘制出如图1-1所示的数据库分类图。
 
图1-1  数据库分类图
上图非常形象地将数据库技术分为两大类：关系型数据库（SQL类）和非关系型数据库（NoSQL类），关系型数据库源源不断地为NoSQL类数据库提供理论依据，也就是说，NoSQL类数据库的发展是以关系型数据库为基础，很多思想和智慧都来源于关系型数据库，比如：事务、分布处理、集群、查询语言等。但NoSQL数据库相对于霸主地位的关系型数据库而言，无疑是一种全新的思维和创新。为进一步分析上述枝繁叶茂的NoSQL数据库，有必要对其进行分类。现有的分类方法多种多样，各方法之间分出来的类或子类还可能存在重叠，主流的方法 （Mikayel Vardanyan依据数据模型的不同给出的一个基本分类）分为四大类。

（1）键值存储（Key-Value）数据库
主要采用哈希表技术，存储特定的键和指向特定的数据指针。该模型简单、易于部署。例如：Redis、Memcached、Riak KV、Hazelcast、Ehcache、Voldemort、Oracle BDB等。
（2）文档型数据库
以嵌入式版本化文档为数据模型，其灵感是来自于Lotus Notes办公软件，支持全文检索、关键字查询等功能。例如：MongoDB、Amazon DynamoDB、Couchbase、CouchDB、SequoiaDB等。
（3）列存储数据库
列存储数据库是指数据存储采用列式存储架构，相比传统的行式存储架构，数据访问速度更快，压缩率更高，支持大规模横向扩展。例如：Cassandra、HBase、Riak、GBase 8a等。
（4）图（Graph）数据库
以图论为理论根基，用节点和关系所组成的图为真实世界直观建模，支持百亿乃至千亿量级规模的巨型图的高效关系运算和复杂关系分析，例如：Neo4j、OrientDB、Titan等。
上述四类NoSQL数据库依据其数据模型的不同，均表现出各自的优势和劣势，以及适应的典型应用场景。具体归类如表1-1所示。
表1-1  NoSQL数据库的四大分类分析
分类 数据模型 优势 劣势 典型应用场景
键值数据库 哈希表 查找速度快 数据无结构化，通常只被当作字符串或者二进制数据 内容缓存，主要用于处理大量数据的高访问负载，也用于一些日志系统等
列存储数据库 列式数据存储架构 查找速度快，支持分布横向扩展，数据压缩率高 功能相对受限 分布式文件系统
文档型数据库 键值对扩展 数据结构要求不严格，表结构可变，不需要预先定义表结构 查询性能不高，缺乏统一的查询语法 Web应用
图数据库 节点和关系组成的图 利用图结构相关算法。比如最短路径，节点度关系查找等 可能需要对整个图做计算，不利于图数据分布存储 社交网络、推荐系统、意向图、消费图、兴趣图、关系图谱等
另一方面，大量的研发人员或团队对五类主流数据库产品（键值数据库、列存储数据库、文档型数据库、图数据库、关系数据库）进行过大量的比较和分析，比较的指标涵盖：性能、可扩展性、复杂性等多个维度。表1-2列出了一个典型的分析结果，它是Ben Scofield在YCSB开源数据库基准测试（Yahoo! Cloud Serving Benchmark）上所测试分析的结果 。


表1-2  各类数据库主要指标分析
分类 性能 可扩展性 灵活性 复杂性 功能性
键值数据库 高 高 高 无 可变（无）
列存储数据库 高 高 一般 低 很少
文档型数据库 高 可变（高） 高 低 可变（低）
图数据库 可变 可变 高 高 图论
关系数据库 可变 可变 低 一般 关系代数
通过上述较为系统全面的分析，无论是从宏观的优劣势和典型应用场景方面，还是微观具体的基准测试方面，之前的问题有了更为清晰的答案。正如数据库领域的布道者、图灵奖得主Michael Stonebraker对数据库未来发展所预言的那样One size will fit none（单一模式不能包打天下），也就是告诫我们需要将更多的精力花在选择最合适的技术去有针对性地高效解决所面临的具体问题，恰恰回归到“具体问题具体分析”这一普适的哲学原理。
4. 图数据库的发展
具体到图数据库而言，相对于传统关系数据库这一“老大哥”就最多只能称作“小老弟”。作为图数据库的领跑者——Neo4j最初发布版本是在2007年，一路奔跑前行至今也不过10年。可见这一新型数据库技术有其固有的、旺盛的生命力，细想不难发现，这来源于：图是一种能对现实世界进行普适直观的建模工具，通俗地说，图无处不在！我们信手就可拈来一大批身边与吃穿住行生活密切相关的图事例，比如人际交往、购物消费、交通网络、旅游规划等。
正如全球著名的信息咨询公司——高德纳咨询公司（Gartner Group）所分析 ：商业世界中有5个非常有价值的图：Social Graph（社交图）、Intent Graph（意向图）、Consumption Graph（消费图）、Interest Graph（兴趣图）、Mobile Graph（移动图），并指出应用这些图的能力是一个“可持续的竞争优势”。
图数据库在数据库领域如此“晚产”，正如其理论基础图论在数学界一样像“新生儿”，图论最早可追溯到图论创始人瑞典数学家欧拉（Leornhard Euler）于1738年解决了柯尼斯堡七桥问题。现在图论应用极其广泛，但大发展时期是20世纪40~60年代，一系列图论相关研究取得了突破性进展，包括：拟阵理论、超图理论、极图理论、代数图论、拓扑图论等。
从之前罗列的数据库领域重要事件和表1-1中所示的内容，细心的读者不难发现：图数据库归类到网状数据库之列，从数据库模型上主要有三大类：层次型、网状型、关系型，网状数据库标准化的出现还早于关系数据模型的提出，而为什么关系型数据库却后来居上，长期占住数据库领域的霸主地位呢？要回答这个问题，其实不难，稍对计算机发展历史有一定了解的人就能较容易地找到答案。从表1-2中单看图数据库和关系数据库两行就不难发现，图数据库的实现复杂性远高于关系数据库；另一方面，再回溯上世纪，回看那时的硬件性能无法跟现在相提并论，单说处理器速度和内存容量，要实现这一令人神往又如此复杂的图数据库谈何容易，完全可以说是一种“奢求”！因此，当时的研发人员只能另辟蹊径，在数据模型上做文章，降低建模的复杂度，采用二维表（在关系数据库中称为“关系”）这一更易于理解和实现的创新性技术来构建数据库。
至此，关系数据库中的“关系”二字，还真是与我们所熟知的，比如人际关系、借贷关系等完全不搭界，仅仅是“关系数据库之父”Edgar Frank Codd在其论文中将：在集合论基础上构建二维表称作关系罢了。那是不是说传统关系型数据库不能存储、管理我们所熟知的这些关系呢？这个显然不是，而是将这些熟知的关系隐藏转化为以集合论为基础的关系代数上的一种常用的连接操作（Join），最终在当时用关系模型的易理解性和理论可行性来超越网状模型之上的图数据库的复杂性，成就了关系型数据库的持久辉煌！
诚然，得益于信息技术的飞速发展，无论是硬件、网络，还是软件等各方面都今非昔比，图数据库自从2007年第一个可商用Neo4j产品的出现，就成为政界、学界、商界、媒界持续关注的焦点，其发展势头绝不亚于当年的关系数据库，俨然成为能高效、便捷、直观地处理海量、快速、多样的数据，并能快速挖掘其中纷繁复杂关系的一把利器！
1.2  图数据库基础
1.2.1  图数据库介绍
图数据库（Graph Database）是基于图论实现的一种新型NoSQL数据库。它的数据存储结构和数据的查询方式都是以图论为基础的。图论中图的基本元素为节点和边，在图数据库中对应的就是节点和关系。
在图数据库中，数据与数据之间的关系通过节点和关系构成一个图结构并在此结构上实现数据库的所有特性，如对图数据对象进行创建、读取、更新、删除（Create、Read、Update、Delete，简称：CRUD）等操作的能力，还有处理事务的能力和高可用性等。
目前市面上较为流行的图数据库产品如图1-2所示。
 
图1-2  较为流行的图数据库
1.2.2  图数据模型
图数据要具体存储到图数据库中，最终落实为具体的数据文件，自然就涉及特定的图数据模型，即如何存、采用什么实现方式来存图数据。常用的有三种：属性图（Property Graphs）、超图（Hypergraphs）和三元组（Triples）。下面分别讨论每种模型。
1.2.2.1  属性图
属性图模型直观更易于理解，能描述绝大部分图使用场景，也是当下最流行的图数据模型。Neo4j采用的就是这种属性图模型。符合下列特征的图数据模型就称为属性图：
? 它包含节点和关系。
? 节点可以有属性（键值对）。
? 节点可以有一个或多个标签。
? 关系有名字和方向，并总是有一个开始节点和一个结束节点。
? 关系也可以有属性。
1.2.2.2  超图
超图是一种更为广义的图模型，在超图中，一个关系（称作超边）可以关联任意数量的节点，无论是开始节点端还是结束节点端，而属性图中一个关系只允许一个开始节点和一个结束节点，因此，超图更适用表示多对多关系。比如常见的房产拥有关系，如图1-3所示，在房产证上张三与李四共同拥有三套房，在超图中就只需一条超边（拥有）就能表示出来。
但现实中，仅仅一条超边来表示拥有关系，可能会隐藏很多细节，例如房产证中每套房张三、李四各自占有的比率，因此，如果用属性图来表示将更为丰富，只是将一条超边转化为6条属性图中的关系，如图1-4所示。
       
图1-3  简单的房产拥有关系超图表示             图1-4  简单的房产拥有关系属性图表示
1.2.2.3  三元组
三元组思想来源于语义网（Semantic Web），虽然迄今为止，只有很少的网络资源是用语义网来表示的，但研究人员发现可以使用带语义的标签网来表示图数据。三元组是一个包含主谓宾的数据结构，例如张三和李四拥有三套房子等。显然，单个三元组的语义还是比较有限，需要借助资源描述框架（Resource Description Framework，RDF）来增强其知识推理及数据关联性。由于按三元组模型来实现的图数据库产品很少，在此不作进一步介绍，有兴趣的读者可以深入查阅语义网的相关资料。
1.2.3  图计算引擎
与关系数据库相同，图数据库的核心也是构建在一个引擎之上的，那就是图计算引擎。图计算引擎是能够组织存储大型图数据集并且实现了全局图计算算法的一种数据库核心构件。
图1-5展示了一个图计算引擎的工作流程。它包括一个具有联机事务处理过程（On-Line Transaction Processing，OLTP）的数据库记录系统，图计算引擎用于响应用户终端或应用程序运行时发来的查询请求，周期性从记录系统中进行数据抽取、转换和加载，然后将数据从记录数据系统读入到图计算引擎并进行离线查询和分析，最后将查询、分析的结果返回给用户终端或应用程序。
 
图1-5  典型图计算引擎工作流程图
目前较为流行的图计算引擎有两种：单机图计算引擎和分布式图计算引擎。
单机图计算引擎的典型代表是Cassovary，Cassovary是一个用Scala编写的基于Java虚拟机的图计算引擎。在Twitter上Cassovary用来为其提供许多基于图的功能，如谁关注了谁、谁被谁关注。
分布式图计算引擎的典型代表是Pegasus和Giraph。Pegasus是一个运行在Hadoop云计算平台之上的分布式图计算引擎，最初它是为了Google的网页数据处理而设计出来的；Giraph是Apache一个高可扩展性图计算项目，它最初起源于Google开发的Pregel图形处理项目。
1.2.4  图数据库的历史
在20世纪60年代中期，Navicational数据库出现，它被认为是图数据库的雏形，这种数据库可以以树状结构的形式存储和组织数据。IBM的IMS也是此类数据库的典型代表。
在20世纪60年代后期，数据库以网络模型的存储与组织形式逐渐衍生出图数据库的概念。1969年，CODASYL为COBOL（一种数据处理领域最为广泛的程序设计语言）定义了网络数据库语言。
20世纪90年代初，为了在网站应用中加速索引网页的性能，图数据库有了较大的改进。
在2005年前后，商业化的具有ACID特性——Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）的图数据库出现了，如：Neo4j、Oracle Spatial、GraphDB等。
在2010年，具有并行扩展功能的ACID图数据库出现，SAP HANA（High-Performance Analytic Appliance，一种高性能分析设备）将列式存储技术引入内存数据库。同期，可同时支持图形、关系、面向文档等多种存储形式的数据库也出现了，例如OrientDB、ArangoDB和MarkLogic。
随着社交应用的普及，社交应用处理复杂网状关系的需求与图数据库的特性自然而然地相互结合了，各种图数据库成为较受欢迎的社交网络数据分析解决方案。
1.3  图数据库与关系数据库的对比
在数据库领域的应用中并不是任何用例都适用于关系数据模型，但在过去由于缺乏可行的替代方案和各大关系数据库厂商的大力发展下，其他类型数据库难以成为主流；但随着图数据库的产生，这种情况发生了改变。
1.3.1  关系数据库的弊端
关系数据库自上世纪80年代以来一直是数据库领域发展的动力，并持续到今天。它们将高度结构化的数据存储在具有某些类型信息的二维表格中，并且由于其组织数据的严格特性，开发人员和应用程序必须严格地按照关系数据库的相关约定来构建其应用程序中使用的数据。
在关系数据库中，通过外键约束来实现两表或多个表之间某些记录相互引用的关系。外键约束是关系数据库中实现表之间相互引用的必不可少的策略。关系数据库通过外键在主表中寻找匹配的主键记录来进行搜索、匹配计算操作，因为这种操作是“计算密集型”的，也是“内存密集型”的，并且操作次数将是表中记录的指数级别，所以它需要消耗大量的系统资源。如果您使用多对多关系，则必须要再添加一个中间表，它用来保存两个参与表的外键对应关系，这进一步增加了连接操作的成本。
1.3.2  图数据模型的优势
在图数据库中，关系是最重要的元素。通过关系我们能够将节点相互关联起来构建与我们的问题领域密切相关的复杂模型。
图数据库模型中的每个节点都直接包含一个关系列表，关系列表中存放此节点与其他节点的关系记录。这些关系记录按类型和方向组织起来，并且可以保存附加属性。无论何时运行类似关系数据库的连接（Join）操作时，图数据库都将使用此列表来直接访问连接的节点，无须进行记录的搜索、匹配计算操作。
将关系预先保存到关系列表中的这种能力使Neo4j能够提供比关系数据库高几个数量级的性能，特别是对于复杂连接的查询，Neo4j能够实现毫秒级的响应。
使用图数据库来组织数据所得到的数据模型比使用传统关系或其他NoSQL数据库的数据模型更简单，同时更具有表现力。
图数据库支持非常灵活和细粒度的数据模型，可以用简单直观的方式对数据应用进行建模和管理，可以更方便地将数据单元小型化、规范化；同时还能实现丰富的关系连接，这样在对数据查询时可以用任何可想象到的方式进行查询操作。可见，与关系数据库相比，图数据库可支持更多类型的用例，如图1-6所示。
 
图1-6  图数据库中关系的丰富表现
众所周知，数据库为确保数据的正确性，创造性地引入了事务概念，即ACID特性。像Neo4j这样的图数据库完全支持ACID事务，包括预写式日志（write-ahead logs）的恢复和异常终止后的恢复，所以永远不会丢失已经被加入数据库的数据。
下面是一个用关系数据模型和图数据模型建模的实例，通过两个E-R图（Entity Relationship Diagram，实体-联系图）可以看出使用图数据库更加简洁、明确地描述数据之间的关系。
如图1-7所示，要使用关系数据库创建一个项目部门组织的存储结构，必须为项目、部门、组织、人员单独创建表结构，各个表结构之间通过外键约束相互关联，对于多对多的复杂关系还必须创建“中间表”（如Department_Members表），通过E-R图可以看出，各个表结构中创建了大量的主键、外键列，并创建了中间表来维护复杂关系，这消耗了大量的系统资源。
 
图1-7  关系数据模型
如果采用图数据库创建一个项目部门组织的存储结构则容易得多，只需要为项目、部门、组织、人员创建节点，并且节点不需要主键、外键，也不需要中间表，只保留必要的属性即可。各个节点直接通过关系指向来表达节点之间的复杂关系。使用图数据库可以更加简洁、明确地描述数据间的复杂关系，如图1-8所示。
 
图1-8  图数据模型
1.4  图数据库与其他 NoSQL 数据库的对比
为了克服关系数据库在大型企业级应用中的弊端，NoSQL数据库逐渐流行起来。NoSQL数据库专注于解决大规模数据集合、多重数据种类带来的挑战，尤其是大数据应用难题。同时NoSQL数据库的多样化也提供了多种不同的数据模型解决方案，每个解决方案都可以应用到不同的项目用例中。显然，Neo4j就是NoSQL中可以提供图数据模型的典型代表。
1.4.1  其他 NoSQL 数据库的弊端
目前大部分NoSQL类数据库的数据存储形式都是基于集合的，数据按照集合被划分开，比如文档数据库中的文档。NoSQL数据库的数据存储在不连贯的集合中，这使得数据之间的相互连接、建立关系变得困难。
要实现类似关系数据库的外键功能，通常人们会将某个数据集合直接嵌入到另一个数据集合中来实现两者之间的从属关系，但很明显这样创建数据集合之间的关系要付出很大的存储开销。
1.4.2  将键值对存储与图数据库相关联
如图1-9所示，键值（Key-Value）存储数据库，其数据按照键值对的形式进行组织、索引和存储，类似Java中的map，它适合不涉及过多数据关系的应用。因为能有效减少读写磁盘的次数，所以其性能非常高。
如果将这些键值对相互关联，就可以得到一个图结构。通过这个图结构，可以表达数据之间的复杂关系，如图1-10所示。
                  
图1-9  键值对存储结构                  图1-10  键值对存储结构与图结构相互关联
1.4.3  将文档存储与图数据库相关联
文档存储的层次化结构可容纳许多无模式的数据，可以轻松地将数据存储为树状结构。虽然树也是一种图形，但树只能表达从下到上的从属关系，如图1-11所示。
在树状存储结构中总会出现多次被嵌入的冗余数据，这增加了更新数据的困难，同时也难以确保数据的一致性。如果我们将冗余的数据去掉，然后用图结构将存在相互关系的数据相关联，数据冗余的问题就解决了，并且数据之间的关系变得更直观，如图1-12所示。
                  
图1-11  文档存储结构              图1-12  文档存储结构与图结构相互关联
1.5  Neo4j 概述
Neo4j是由Java实现的开源NoSQL图数据库。自2003年开始研发，直到2007年正式发布第一版。Neo4j的源代码托管在GitHub上，技术支持托管在Stack Overflow和Neo4j Google讨论组上。Neo4j现如今已经被各种行业的数十万家公司和组织采用。Neo4j的使用案例涵盖了网络管理、软件分析、科学研究、路由分析、组织和项目管理、决策制定、社交网络等诸多方面。
Neo4j实现了专业数据库级别的图数据模型的存储。与普通的图处理或内存级数据库不同，Neo4j提供了完整的数据库特性，包括ACID事务的支持、集群支持、备份与故障转移等，这使其适合于企业级生产环境下的各种应用。
另外，Neo4j一些特殊功能使得Neo4j在用户、开发人员和DBA中非常受欢迎（如图1-13所示）。
? 一个本地化的图数据库：Neo4j自底向上构建成一个图数据库。它的体系结构旨在优化快速管理、存储和遍历节点和关系。在Neo4j中，关系是数据库中最重要的元素，它代表节点之间的相互联系。众所周知，在关系数据库领域中，“关系”用于多个不同表之间的连接操作，这种操作的性能下降与关系的数量呈指数级别的，但在Neo4j中则是用于从一个节点指向另一个节点，其性能却是线性级别的。
? 界面友好：Neo4j提供了一个查询与展示一体化的Web操作界面。对于图数据模型Neo4j使用D3.js做数据可视化，非常形象地展示了数据模型的节点和关系。
? 声明式图查询语言：Cypher是一种声明式图数据库查询语言，它表现力丰富，查询效率高，其地位和作用与关系型数据库中的SQL语言（Structured Query Language，结构化查询语言）类似。Cypher还有良好的扩展性，用户可以定制自己的查询方式（如自定义过程）。
? ACID事务：Neo4j通过ACID事务提供真正的数据安全，Neo4j使用事务来保证数据在硬件故障或系统崩溃的情况下不会丢失。
? 高性能：Neo4j使用多副本主从复制的方式构建高可靠性集群，支持大数据集合并且可以不断扩展其容量，可存储数百万亿个实体。也就是说，Neo4j可部署在一个可容错、可扩展的集群上。此外Neo4j还提供热备份和性能监控功能。
? 代码开源：Neo4j将源代码公布到GitHub，任何人都可以去Neo4j的GitHub主页下载源代码。
 
图1-13  Neo4j支持的特性
当然，传统的关系数据库经过长期的发展，其特性、性能已经被企业级应用认可，并且新兴的其他NoSQL数据库也越来越多地被使用在企业级项目的数据存储解决方案中；那么Neo4j这种图数据库与关系数据库、NoSQL数据库对比，其优势是什么呢？ Neo4j与其他数据库的对比情况如表1-3所示。


表1-3  Neo4j与其他数据库的对比
性能 关系数据库 其他NoSQL数据库 Neo4j
数据存储 关系数据库的数据存储在一个预定义好的、结构固定的二维表格中，数据之间的关系靠各个表格行列之间相互关联实现，查询效率低下 其他NoSQL不支持数据库级别的数据连接操作。性能和数据可信度随着连接的规模和复杂程度的增加而降低 Neo4j采用具有自由邻接特性的图存储结构，能够提供更快的事务处理和数据关系处理功能
数据模型 关系数据库模型必须与建模者一起开发，并从逻辑模型转换为物理模型。由于数据类型和来源必须提前知道，所以后续的任何更改都会导致很大的结构变动，这对项目是很不利的
其他NoSQL数据模型不适合企业架构将其用来作为广泛的列和文档存储，不能在设计层面提供控制 Neo4j提供灵活的数据模型，逻辑模型和物理模型之间不会相互耦合。可以随时、随意添加或更改数据和数据类型，从而大大缩短开发时间，实现项目真正的敏捷、迭代开发
数据查询性能 在关系数据库的多表联合查询中，数据处理性能严重受限于连接操作，如果单个表的行数过大，即便是很简单的连接查询也会耗费大量性能资源 其他NoSQL支持复杂数据关系的处理能力较弱，因此必须在应用程序级处理所有的数据关系 Neo4j使用图存储结构，数据之间的关系附加在节点上，无论关系的数量或深度如何都能确保零延迟和实时性能
查询语言 SQL查询语言，其复杂性会随连接数据查询所需的JOIN操作的数量而增加 各种NoSQL数据库的查询语言有所不同，但都没用于表达数据关系的机制
Cypher是一种图查询语言，提供了描述关系查询的最有效的表达方式

事务处理 企业应用程序需要使用关系数据库的ACID事务支持，以确保数据的一致性和可靠性 其他NoSQL基本无法提供ACID事务，因为其数据关系的基本可用性和最终一致性是不可靠的 Neo4j可以为企业应用程序提供ACID事务来保持全面一致和可靠的数据
数据库的扩展性 关系数据库通过主从服务器间的复制进行扩展，成本很高。如果数据表之间有多种复杂关系，这种扩展会降低集群的整体性能 其他NoSQL的扩展可以提升数据的写入性能但不能提升数据的读取性能，不能保证数据的可靠性 Neo4j本质上适用于基于模式的查询。其扩展架构通过主从服务器间的复制来维护数据完整性。支持IBM POWER8和CAPI Flash系统进行大规模扩展
创建大规模数据中心 关系数据库可以通过服务器整合来创建大规模数据中心，但是其扩展架构是很昂贵的 使用NoSQL可以不断向其扩展架构中添加新硬件，但其不考虑能源成本、网络漏洞和其他风险
Neo4j可以更高效地使用硬件，从而降低成本
1.6  Neo4j 的体系结构
本节将从数据库的底层设计揭开Neo4j数据库的神秘面纱，了解Neo4j为了实现图的存储所采用什么样的体系结构，揭秘为什么图数据库基于复杂联系的查询相比关系型数据库要更快。
Neo4j最初的设计动机是为了更好地描述实体之间的联系。现实生活中，每个实体都与周围的其他实体有着千丝万缕的关系，这些关系里存在着大量的潜在信息。但是传统的关系型数据库更加注重刻画实体内部的属性，实体与实体之间的关系主要通过外键来实现。因此，在查询一个实体的关系时需要join操作，特别是深层次的关系查询需要大量的join操作，而join操作通常又非常耗时。随着现实世界中关系数据的急剧增加，导致关系型数据库已经逐渐地难以承载查询海量数据深层次关系需要大量数据库表操作带来的运算复杂性，Neo4j在这样的情况下应运而生。
1.6.1  免索引邻接
Neo4j有一个重要的特点，就是用来保证关系查询的速度，即免索引邻接属性，数据库中的每个节点都会维护与它相邻节点的引用。因此每个节点都相当于与它相邻节点的微索引，这比使用全局索引的代价要小得多。这就意味着查询时间和图的整体规模无关，只与它附近节点的数量成正比。在关系型数据库中使用全局索引连接各个节点，这些索引对每个遍历都会增加一个中间层，因此会导致非常大的计算成本。而免索引邻接为图数据库提供了快速、高效的图遍历能力。
对比图1-14和图1-15，可以明显地看出关系型数据库与Neo4j在查找关系时的区别。
 
图1-14  RDBMS中关系查询示意图
 
图1-15  Neo4j中关系查询示意图
图1-14展示了在RDBMS（关系型数据库）中的查询方式。要查找Alice所购买的东西，首先要执行关系表的索引查询，时间成本为O(log(n))，n为索引表的长度。这对于偶尔的浅层次查询是可以接受的，但是当查询的层次变深或者是执行反向查询时代价将会变得不可接受了。如果相较于查询Alice购买的东西，要查询某件商品被哪些人购买了（推荐引擎中常用的一个场景），将不得不使用暴力方法来遍历整个索引，时间复杂度则将增长到O(n)。除非我们再建立一个从商品到用户的索引表，但是该方法将会占用许多额外空间，并且使索引变得难以维护。
如果我们再考虑一个更复杂的场景，Alice购买过的商品被哪些人购买过（推荐引擎中查找有共同爱好的人），找到Alice购买过的商品的时间成本为O(log(n))，找到每个商品被哪些人购买的时间成本为O(n)，假如Alice购买过m（m远小于n）个商品，那么总的时间复杂度即为O(mnlog(n))。即使再建立一个方向索引表，时间复杂度也为O(mn)。
图1-15展示了在同样的场景下Neo4j的查询方式。使用免索引近邻机制，每个节点都有直接或间接指向其相邻节点的指针。要查找Alice买过的东西，只需要在Alice的关系链表中遍历，每次的遍历成本仅为O(1)。要查找一个商品被哪些人购买了，只要跟随指向该商品的关系来源即可，每次的遍历成本也是O(1)。更复杂的，要查找Alice购买过的东西被哪些人购买过，时间复杂度也仅为O(m)，其中m远小于n。这相较于RDBMS的时间复杂度还是占有绝对的优势。
免索引邻接针对RDBMS中的关系查询的两个缺点做了改进：
（1）免索引邻接使用遍历物理关系的方法查找，比起全局索引来说代价要小得多。查询一个索引一般的时间复杂度为O(log(n))，而遍历物理关系的时间复杂度仅为O(1)，至少对于Neo4j的存储结构来说是如此。
（2）当索引建立之后在试图反向遍历时，建立的索引就起不到作用了。我们有两个选择：对每个反向遍历的场景创建反向查找索引，或者使用原索引进行暴力搜索，而暴力搜索的时间复杂度为O(n)。这种代价相对于很多需要实时操作的场景来说是不可接受的。
利用免索引邻接机制，在图数据库上进行关系查询效率非常高，这种高效是建立在图数据库注重关系的架构设计之上的。
1.6.2  Neo4j 底层存储结构
免索引邻接是图数据库实现高效遍历的关键，那么免索引邻接的实现机制就是Neo4j底层存储结构设计的关键。能够支持高效的、本地化的图存储以及支持任意图算法的快速遍历，是使用图数据库的重要原因。本节将深入地探索Neo4j的底层存储结构。
从宏观角度来说，Neo4j中仅仅只有两种数据类型：
（1）节点（Node）：节点类似于E-R图中的实体（Entity）。每一个实体可以有零个或多个属性（Property），这些属性以key-value对的形式存在。属性没有特殊的类别要求，同时每个节点还具有相应的标签（Label），用来区分不同类型的节点。
（2）关系（Relationship）：关系也类似于E-R图中的关系（Relationship）。一个关系有起始节点和终止节点。另外，与节点一样，关系也能够有自己的属性和标签。
节点和关系在Neo4j中如图1-16所示。
 
图1-16  Neo4j基本存储结构示意图
节点和关系分别采用固定长度存储，图1-17为Neo4j 节点和关系存储文件的物理结构。
 
图1-17  Neo4j节点和关系存储文件的物理结构
节点存储文件用来存储节点的记录，文件名为neostore.nodestore.db。节点记录的长度为固定大小，如图中所示，每个节点记录的长度为9字节。格式为：Node:inUse+nextRelId+ nextPropId。
? inUse：1表示该节点被正常使用，0表示该节点被删除。
? nextRelId：该节点的下一个关系ID。
? nextPropId：该节点的下一个属性ID。
我们可以将neostore.nodestore.db中存储的记录看作是如下方式：
Node[0,used=true,rel=9,prop=-1]
Node[1,used=true,rel=1,prop=0]
Node[2,used=true,rel=2,prop=2]
Node[3,used=true,rel=2,prop=4]
Node[4,used=true,rel=4,prop=6]
Node[5,used=true,rel=5,prop=8]
Node[6,used=true,rel=5,prop=10]
Node[7,used=true,rel=7,prop=12]
Node[8,used=true,rel=8,prop=14]
Node[9,used=true,rel=8,prop=16]
Node[10,used=true,rel=10,prop=18]
Node[11,used=true,rel=11,prop=20]
Node[12,used=true,rel=11,prop=22]采用固定字节长度的记录可以快速地查询到存储文件中的节点。如果有一个ID为100的节点，我们知道该记录在存储文件中的第900字节。基于这种查询方式，数据库可以直接计算一个记录的位置，其成本仅为O(1)，而不是执行成本为O(log(n))的搜索。
关系存储文件用来存储关系的记录，文件名为neostore.relationshipstore.db。像节点的存储一样，关系存储区的记录大小也是固定的。格式为：Relationship:inUse+firstNode+secondNode+relType+firstPrevRelId+firstNextRelId+secondPrevRelId+secondNextRelId+nextPropId。
? inUse，nextPropId：作用同上。
? firstNode：当前关系的起始节点。
? secondNode：当前关系的终止节点。
? relType：关系的类型。
? firstPrevRelId & firstNextRelId：起始节点的前一个和后一个关系的ID。
? secondPrevRelId & secondNextRelId：终止节点的前一个和后一个关系ID。
同样的，“neostore.relationshipstore.db”中存储的记录也可以看作是如下的方式：
Relationship[0,used=true,source=1,target=0,type=0,sPrev=1,sNext=-1,tPrev=3,tNext=-1,prop=1]
Relationship[1,used=true,source=2,target=1,type=1,sPrev=2,sNext=-1,tPrev=-1,tNext=0,prop=3]
Relationship[2,used=true,source=3,target=2,type=2,sPrev=-1,sNext=-1,tPrev=-1,tNext=1,prop=5]
Relationship[3,used=true,source=4,target=0,type=0,sPrev=4,sNext=-1,tPrev=6,tNext=0,prop=7]
Relationship[4,used=true,source=5,target=4,type=1,sPrev=5,sNext=-1,tPrev=-1,tNext=3,prop=9]
Relationship[5,used=true,source=6,target=5,type=2,sPrev=-1,sNext=-1,tPrev=-1,tNext=4,prop=11]
Relationship[6,used=true,source=7,target=0,type=0,sPrev=7,sNext=-1,tPrev=9,tNext=3,prop=13]
Relationship[7,used=true,source=8,target=7,type=1,sPrev=8,sNext=-1,tPrev=-1,tNext=6,prop=15]
Relationship[8,used=true,source=9,target=8,type=2,sPrev=-1,sNext=-1,tPrev=-1,tNext=7,prop=17]
Relationship[9,used=true,source=10,target=0,type=0,sPrev=10,sNext=-1,tPrev=-1,tNext=6,prop=19]
Relationship[10,used=true,source=11,target=10,type=1,sPrev=11,sNext=-1,tPrev=-1,tNext=9,prop=21]
Relationship[11,used=true,source=12,target=11,type=2,sPrev=-1,sNext=-1,tPrev=-1,tNext=10,prop=23]
Neo4j中有一个 .id文件用来保持对未使用记录的跟踪，用来回收未使用的记录占用的空间。节点和关系的存储文件只关心图的基本存储结构而不是属性数据。这两种记录都使用固定大小的记录，以便存储文件内的任何记录都可以根据ID快速地计算出来。这些都是强调Neo4j高性能遍历的关键设计决策。节点记录和关系记录都是相当轻量级的：只由几个指向联系和属性列表的指针构成。
图1-18是Neo4j中的其他常见的基本存储类型，需要注意的是属性的存储，属性记录的物理存储放置在neostore.propertystore.db文件中。与节点和关系的存储记录一样，属性的存储记录也是固定长度。每个属性记录包含4个属性块和属性链中下一个属性的ID。属性链是单向链表，而关系链是双向链表。一个属性记录中可以包含任何Java虚拟机（JVM）支持的基本数据类型、字符串、基于基本类型的数组以及属性索引文件（neostore.propertystore.db.index）。属性索引文件主要用于存储属性的名称，属性索引的值部分存储的是指向动态内存的记录或者内联值，短字符串和短数组会直接内联在属性存储记录中。当长度超过属性记录中的propBlock长度限制之后，会单独存储在其他的动态存储文件中。
 
图1-18  Neo4j其他常见的物理结构
Neo4j中有两种动态存储：动态字符串存储（neostore.propertystore.db.strings）和动态数组存储（neostore.propertystore.db.arrays）。动态存储记录是可以扩展的，如果一个属性长到一条动态存储记录仍然无法完全容纳时，可以申请多个动态存储记录逻辑上进行连接。
1.6.3  Neo4j 的遍历方式
我们可以看到磁盘上各种存储文件存在交互。每个节点记录都包含一个指向该节点的第一个属性的指针和联系链中第一个联系的指针。要读取一个节点的属性，从指向第一个属性的指针开始，遍历整个单向链表结构。要找到一个节点的关系，从指向的第一个关系开始，遍历整个双向链表，直到找到了感兴趣的关系。一旦找到了感兴趣关系的记录，我们就可以与使用和查找节点属性一样的方法查找关系的属性（如果该关系存在属性）。我们也可以很方便地获取起始节点和结束节点的ID，利用节点ID乘以节点记录的大小（9字节）就可以立即算出每个节点在节点存储文件中的具体位置，所需的复杂度仅为O(1)。
图1-19就是节点、关系、属性在Neo4j中的物理表现方式。图中直接看起来可能不是那么直观，可以想象关系是属于两个节点的，但是一个关系也不应该在记录中出现两次，这样会造成内存的浪费。因此两个双向链表之间会有指针，一个是起始节点可见的列表关系，另一个是结束节点可见的列表关系。每一个列表都是双向链表，因此我们可以在任何一个方向上进行快速遍历和高效地插入和删除。
 
图1-19  在Neo4j中的物理存储方式
下面通过一个例子来讲解Neo4j遍历关系和节点的详细过程。假如在Neo4j中存储了A、B、C、D、E 5个节点和R1、R2、R3、R4、R5、R6、R7 7个关系，它们之间的关系如图1-20所示。
 
图1-20  Neo4j中的一个关系结构示意图
假如要遍历图中节点B的所有关系，只需要向NODEB-NEXT方向遍历，直到指向NULL为止，可以从图1-21中看出节点B的所有关系为R1、R3、R4、R5。
 
图1-21  Neo4j中的图遍历方式
通过固定大小的存储记录和指针ID，只要跟随指针就可以简单地实现遍历并且高速执行。要遍历一个节点到另一个节点的特定关系，在Neo4j中只需要遍历几个指针，然后执行一些低成本的ID计算即可，这相较于全局索引的时间复杂度要低很多，这就是Neo4j实现高效遍历的秘密。
? 从一个给定节点定位关系链中第一个关系的位置，可以通过计算它在关系存储的偏移量来获得。跟获得节点存储位置的方法一样，使用关系ID乘以关系记录的固定大小即可找到关系在存储文件中的正确位置。
? 在关系记录中，搜索第二个字段可以找到第二个节点的ID。用节点记录大小乘以节点ID可以得到节点在存储中的正确位置。
1.6.4  Neo4j 的存储优化
Neo4j支持存储优化（压缩和内联存储属性值），对于某些短字符的属性可以直接存储在属性文件中（neostore.propertystore.db）。在实际操作中，像邮政编码、电话号码这样的短字符串属性就可以直接内联到属性存储文件，而不是单独地放在另一个动态存储区，这样将大幅减少I/O操作并且增大吞吐量，因为只有一个文件需要访问。
除了可以内联属性值，Neo4j还可以对属性名称的空间严格维护，例如在社交网络中，有可能会有多个节点存在first_name和last_name这样的属性。如果将每个属性都逐字写入到磁盘上就会造成浪费。因此，替代方案是属性名称都通过属性索引文件从属性存储中间接引用。属性索引允许所有具有相同名称的属性共享单个记录，因而Neo4j可以节省相当大的空间和I/O开销。
即使现在的磁盘访问速度已经很快了，但是CPU访问磁盘仍然比CPU直接访问高速缓存要慢得多。因此，Neo4j也采用了缓存策略，保证那些经常访问的数据可以快速地被多次重复访问。Neo4j高速缓存的页面置换算法是基于最不经常使用的页置换（LFU，Least Frequently Used）缓存策略，根据页的常用程度进行微调。也就是说即使有些页面近期没有使用过，但是因为以前的使用频率很高，那么在短期之内它也是不会被淘汰的。该策略保证了缓存资源在统计学上的最优配置。