To propose a different perspective, a relationship in a graph db is like a materialized join. You pay on relationship creation (you might be using index lookups to find the nodes to connect, similar to a relational db), then for traversal it's just pointer hopping across the relationships to the connected nodes. Aside from the initial lookup of starting node(s), traversing the graph won't use indexes at all, so becomes constant time operations.