ablog

不器用で落着きのない技術者のメモ

Graph Database の物理的なデータ構造

Graph Database の物理的なデータ構造の実装例がどうなっているか調べてみた。

Graph Databases: New Opportunities for Connected Data

Graph Databases: New Opportunities for Connected Data

の "Chapter 6. Graph Database Internals" の説明が分かりやすい。

Native Graph Processing
(中略)
A database engine that utilizes index-free adjacency is one in which each node maintains direct references to its adjacent nodes. Each node, therefore, acts as a micro-index of other nearby nodes, which is much cheaper than using global indexes. It means that query times are independent of the total size of the graph, and are instead simply proportional to the amount of the graph searched.

A nonnative graph database engine, in contrast, uses (global) indexes to link nodes together, as shown in Figure 6-1. These indexes add a layer of indirection to each traversal, thereby incurring greater computational cost. Proponents for native graph processing argue that index-free adjacency is crucial for fast, efficient graph traversals.


Neo4Jではソースコードはこのあたりだろうか。

package org.neo4j.io.fs;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileLock;

public class StoreFileChannel implements StoreChannel
{
    private final FileChannel channel;

    public StoreFileChannel( FileChannel channel )
    {
        this.channel = channel;
    }

(中略)

    @Override
    public int read( ByteBuffer dst, long position ) throws IOException
    {
        return channel.read( dst, position );
    }

    @Override
    public void readAll( ByteBuffer dst ) throws IOException
    {
        while ( dst.hasRemaining() )
        {
            int bytesRead = channel.read( dst );
            if ( bytesRead < 0 )
            {
                throw new IllegalStateException( "Channel has reached end-of-stream." );
            }
        }
    }