그래프 데이터베이스에서 검색 쿼리의 시간 복잡도는 무엇입니까 (특히 Neo4j)?그래프 데이터베이스에서 검색 쿼리의 시간 복잡도는 얼마입니까?
나는 나와 관계형 데이터를 가지고있다. 나는 관계형 데이터베이스 또는 그래프 데이터베이스을 사용하여 해당 데이터를 저장하는 것을 혼란스럽게 생각합니다. 따라서 특정 데이터베이스에 대한 쿼리의 성능 및 시간 복잡도를 기반으로 데이터를 저장하려고합니다. 그러나 그래프 데이터베이스에 대한 쿼리의 성능과 시간 복잡성을 찾을 수 없습니다.
아무도 도와 줄 수 있습니까?
시간 복잡성은 대개 쿼리에서 수행하는 작업 (쿼리 계획자의 결과)에 따라 달라 지므로 그 대답은 간단하지 않습니다. 모든 검색어.
나는 Neo4j에 대해 말할 수 있습니다 (면책 조항 : 저는 Neo4j 직원입니다).
Neo4j의 Lucene 색인 조회는 대개 색인으로 시작 노드를 찾는 경우에만 수행되며 조회 실행 시간의 일부만 나타 내기 때문에 많이 언급하지 않습니다. 관계 트래버 설은 실제 차이점이 표시되는 경향이 있습니다.
시작 노드가 발견되면 Neo4j는 관계 순회를 통해 그래프를 보냅니다. Neo4j는 기본적으로 네이티브 그래프 dbs가 관계형 dbs를 능가하는 경향이있는 메모리를 통한 포인터 쫓기입니다. 포인터를 추적하는 비용은 순회마다 일정합니다.
관계형 dbs (관계형 db 위에 구축 된 그래프 레이어 포함)의 경우 관계 탐색은 일반적으로 O (1)이 아닌 고유 한 시간 복잡성을 갖는 다양한 테이블 조인 알고리즘에 의해 수행되지만 일반적으로 확장되지 않습니다 조인 횟수가 늘어남 (특히 자체/재귀 조인).
이렇게하면 Neo4j와 같은 네이티브 그래프 데이터베이스가 연결된 데이터에 대한 쿼리를 처리 할 수 있습니다. 특히 사소한 증가 또는 증가하는 관계 트래버 설 (또는 reachability 쿼리, 최단 경로 , 다른 사람). 쿼리 비용은 데이터베이스의 총 노드 수가 아닌 쿼리가 접촉하거나 걸었던 그래프 부분과 관련되어 있으므로 쿼리가 DB의 가장 작은 하위 그래프를 터치하도록 적절하게 제한 할 수있을 때 도움이됩니다.
관계형 또는 그래프 데이터베이스를 사용할 것인지에 관한 한 귀하의 데이터와 실행하려는 쿼리의 연결성에 따라 달라집니다.
그래프 데이터베이스를 결정한 경우 네이티브 및 비 네이티브 구현 (Neo4j는 네이티브 그래프 데이터베이스이며 인덱스가없는 기능을 활용하는 등의 다른 기준 집합도 여기에 있습니다. ACI (Neo4는 ACID 데이터베이스)가 필요한지, 풍부하고 풍부한 쿼리 언어 (Neoch4j의 쿼리 언어 인 Cypher)를 원한다면 자유롭게 다른 사람들과 배우고 비교할 수 있습니다.
자세한 내용은 Why Graph Databases Outperfrom RDBMS on Connected Data의 DZone 기사 및 Neo4j의 수석 과학자 인 Jim Webber의 Explaining Graph Databases to a Developer에 대한 기사를 참조하십시오.
사실, 가장 가능성이 높은 시나리오는 에게 모두 Neo4j 및 일부 DBMS (몽고와 같은 관계형 또는 NoSQL에)를 사용하는 것입니다. Neo4j에 모든 데이터 세트를 저장하기가 너무 어렵 기 때문입니다.
DBMS의 속도 순회 노드는 Neo4j보다 10-100 배 이상 느립니다. 또한 Neo4j에는 shortestPath (및 기타 여러 가지) 메소드가 내장되어 있습니다.
또한 ArangoDB와 같은 하이브리드 솔루션을 언급 할 수 있습니다. 그것은 그래프 엔진 + 문서 기반 엔진을 가지고 있습니다. 그러나 두드러진 부분은 두 개의 별도 테이블이므로 Neo4j + DBMS만큼이나 불편합니다.
도 참조하십시오. 관련이 있지만 정확하게 일치하지는 않습니다 https://stackoverflow.com/questions/22821269/performance-of-arbitrary-queries-with-neo4j/22821528#22821528 – FrobberOfBits