今天，我们需要讨论一个很简单但是也很容易被忽略的问题，我们要通过模拟现实世界中的情形，通过理论和实验的方式分析不同的图模型在neo4j中的构建及其性能。
这里我们通过旅客坐火车这个很简单的例子，来建立人与人之间的关系，最终目的是能够寻找出任意指定的2个人之间的关系（换言之就是寻找这两个人之间的最短路径）
我们采用了2种不同的方式来建立模型：
模型1:建立2类节点：人节点、车节点，1类关系：人坐车关系，当某个人乘坐了某趟车，那么他们之间就建立了人坐车的关系。
模型2:建立1类节点：人节点，1类关系：人与人之间的关系，当一个人与另一个人之间存在乘坐同一趟车的情形时，那么这2个人直接就存在一个关系。
我们首先来进行实验分析，我会通过不同规模的数据集来分析：
一、采用403个人，4趟车，其中每一百人共同乘坐一趟车，另外3个人是用来建立连接的，具体可以直接参考数据（附后），当采用模型1时来分析数据时：
当采用模型2时：
可以看出，模型1和模型2寻找最短路径的时间分别为680ms和616ms
二、采用4003个人，4趟车，其中每一千人共同乘坐一趟车，另外3个人是用来建立连接的，当采用模型1来进行分析时：
当采用模型2时：
可以看出，模型1和模型2寻找最短路径的时间分别为748ms和4505ms，相差大约6倍。
三、采用20003个人，4趟车，其中每五千人共同乘坐一趟车，另外3个人是用来建立连接的，当采用模型1来进行分析时：
当采用模型2时：
可以看出，模型1和模型2寻找最短路径的时间分别为1343ms和67948ms，相差大约50倍。
四、采用40003个人，4趟车，其中每一万人共同乘坐一趟车，另外3个人是用来建立连接的，当采用模型1来进行分析时：
当采用模型2时：
可以看出，模型1和模型2寻找最短路径的时间分别为1503ms和296162ms，相差大约197倍。
通过以上的实验可以看出来，当数据量不大的时候，2种模型的查找时间相差不大，当节点和关系量上升时，2种模型的查找时间相差非常巨大。
下面我们从理论上分析下这个问题：
根据neo4j的文档介绍，neo4j采用的是双向广度优先搜索算法来进行最短路径问题的处理，其算法的复杂度为O(V+E)，其中V代表图的顶点数，E代表图的边数。
对于第一种情形，模型1导入 407个结点，406个关系，模型2导入 403个结点，20402个关系，2者相差不大
对于第二种情形，模型1导入4007个结点，4006个关系，模型2导入4003个结点，2004002个关系，可以看到模型2的关系数量上升比较快
对于第三种情形，模型1导入20007个结点，20006个关系，模型2导入20003个结点，50020002个关系，关系差不多达到5000多万个
对于最后一种情形，模型1导入40007个结点，40006个关系，模型2导入40003个结点，200040002个关系，关系差不多达到2亿多个
这里理论分析出来的结果和实验的结果基本符合，通过这样的分析和实验可以看出，当节点数量基本固定的情况下，尽量减少模型中的关系数量，对提高搜索的效率有很大的帮助。
附（数据）：
链接:https://pan.baidu.com/s/1AxmymxTgWPuYRN99DBRzLA 密码:smwx
网友评论