图数据库通过直接导航节点之间的连接来执行图遍历，使用关系作为路径。 当遍历开始时，数据库从一个或多个入口点（节点）开始，并按照查询中定义的特定关系类型和方向进行遍历。 例如，一个查询可能从一个“用户”节点开始，遍历“朋友”关系，并返回三个跳跃内的所有连接用户。 遍历引擎跟踪访问过的节点以避免循环，并在每个步骤应用过滤器或条件，例如检查节点属性或限制遍历深度。 这个过程针对速度进行了优化，因为图数据库以原生方式存储关系，避免了关系数据库中典型的昂贵的连接操作。
图遍历中的一个关键机制是无索引邻接，其中节点直接引用它们连接的关系和相邻节点。 在像 Neo4j 这样的数据库中，每个节点都维护指向其传入和传出关系的指针，允许引擎“行走”图，而无需搜索全局索引。 例如，查找购买特定商品的客户购买的所有产品涉及从商品节点开始，遍历“已购买_BY”关系到客户节点，然后从这些客户遍历“已购买”关系到其他产品。 这种直接导航避免了索引查找的需要，从而使多跳查询变得高效。 像广度优先或深度优先搜索这样的遍历策略是根据查询模式选择的，并且一些数据库允许提示来优化路径查找。
图数据库使用诸如缓存邻接列表、跨关系并行化操作以及在路径不满足条件时提前修剪路径等技术进一步优化遍历。 例如，Apache Age 使用 PostgreSQL 的存储以及特定于图的优化来批量处理关系。 Cypher (Neo4j) 或 Gremlin (Amazon Neptune) 等语言的查询以声明方式表达遍历，让引擎处理执行细节。 像 MATCH (u:User)-[:FRIENDS_WITH*1..3]->(f:User) RETURN f 这样的查询显式定义了遍历深度和关系类型，使数据库能够应用优化，例如限制中间结果的内存使用。 这些功能使图数据库特别适用于社交网络、欺诈检测或推荐系统，在这些系统中，基于关系的查询频繁且复杂。