I would say they are reasonably efficient.

Of course many orders of magnitude slower than keeping it all in in memory maps and doing the traversal there, but fast enough to not be a limiting factor.

Traversing a medium depth DAG with a million nodes to find orphaned nodes takes less than a second on average hardware.

One thing to be aware of is that SQLite has lots of tuning options, and they are all set to very conservative values by default.

E.g. the default journal mode is FULL, which means that it will flush all the way to disk after each write. The default cache size is tiny.

With a bit of tuning you can get quite decent performance out of SQLite while still having full ACID guarantees, or very good performance for cases where you can compromise on the ACID stuff.

I have not yet found a situation where nosql databases like leveldb offer an orders of magnitude advantage over SQLite, and SQLite is so much more powerful and robust...

https://danluu.com/file-consistency/

> I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query.

I'm not sure if this is possible in SQLite, as far as I know the WITH clause is limited to SELECT statements.

> Are they actually efficient in sqlite even for trees?

Recursive common table expressions work by adding returned rows to a queue and then performing the recursive select statement independently on each row in the queue until it's empty.

You can use WITH RECURSIVE to traverse a tree by adding the root node to the queue and recursively visiting adjacent rows until the queue is empty. This works correctly and quickly because trees have only a single path between nodes. If you try the same query on a DAG though it will return every path to a given node, you then have to perform a GROUP BY to find the shortest path outside of the recursive query. In the worst case, if you have a graph with many paths between nodes, this method is exponentially slower than a standard BFS.