You can write the CTE anchor any way you like. If you prefer NOT EXISTS syntax over IS NULL, go for it. The anchor could even reference different table(s) to the recursive part if that suited better.

As for performance - assuming you're using an adjacency list and have indexes in place I'd think the null would be faster.

Finding a given value in a BTree is an O(log n) operation. Reading each value in parent_id then seeing if it is present in child_id will be O(n log n).

You can write the CTE anchor any way you like. If you prefer NOT EXISTS syntax over IS NULL, go for it. The anchor could even reference different table(s) to the recursive part if that suited better.

As for performance - assuming you're using an adjacency list and have indexes in place I'd think the null would be faster.

Finding a given value in a BTree is an O(log n) operation. Reading each value in parent_id then seeing if it is present in child_id will be O(n log n).

If you have completely free choice of design performance comes down to the read/ write ratio and what result sets are desired. One of the other implementations may give much better read performance at the cost of additional work during writes.

You can write the CTE anchor any way you like. If you prefer NOT EXISTS syntax over IS NULL, go for it. The anchor could even reference different table(s) to the recursive part if that suited better.

You can write the CTE anchor any way you like. If you prefer NOT EXISTS syntax over IS NULL, go for it. The anchor could even reference different table(s) to the recursive part if that suited better.

As for performance - assuming you're using an adjacency list and have indexes in place I'd think the null would be faster.

Finding a given value in a BTree is an O(log n) operation. Reading each value in parent_id then seeing if it is present in child_id will be O(n log n).