  Graph database management systems (GDBMSs) are highly optimized to perform
fast traversals, i.e., joins of vertices with their neighbours, by indexing the
neighbourhoods of vertices in adjacency lists. However, existing GDBMSs have
system-specific and fixed adjacency list structures, which makes each system
efficient on only a fixed set of workloads. We describe a new tunable indexing
subsystem for GDBMSs, we call A+ indexes, with materialized view support. The
subsystem consists of two types of indexes: (i) vertex-partitioned indexes that
partition 1-hop materialized views into adjacency lists on either the source or
destination vertex IDs; and (ii) edge-partitioned indexes that partition 2-hop
views into adjacency lists on one of the edge IDs. As in existing GDBMSs, a
system by default requires one forward and one backward vertex-partitioned
index, which we call the primary A+ index. Users can tune the primary index or
secondary indexes by adding nested partitioning and sorting criteria. Our
secondary indexes are space-efficient and use a technique we call offset lists.
Our indexing subsystem allows a wider range of applications to benefit from
GDBMSs' fast join capabilities. We demonstrate the tunability and space
efficiency of A+ indexes through extensive experiments on three workloads.
