Postgresql extension pageinspect – mean bt_metap

Let me know if this helps. This is using MSSQL (T-SQL) syntax so you might have to adjust it for postgres, but, using a temp table called #tree, containing the two columns id and parent and populated as your example is with

SELECT 1, 0
UNION 
SELECT 2, 1
UNION 
SELECT 3, 1
UNION
SELECT 4, 2
UNION 
SELECT 5, 2
UNION 
SELECT 6, 4
UNION
SELECT 7, 6
UNION 
SELECT 8, 6:

with cte as
(
    select id as currentnode, id as root
    from #tree
    union all
    select t.id as currentnode, cte.root 
    from #tree t join cte on t.parent = cte.currentnode
)
select *
from cte
order by root

The above recursive CTE will yield all nodes reachable starting from some root. You can do:

SELECT root, count(*)
from cte
group by root

The count(*) query should yield,

root   |  count
----------------
  1    |    8
  2    |    6
  3    |    1
  4    |    4
  5    |    1
  6    |    3
  7    |    1
  8    |    1

You could then subtract 1 from each of those to get the result you were hinting at. Is this what you were looking for? Even if not, I feel like a recursive CTE can probably help with what you need.

The following requirement can be easily implemented with a constraint: any user can refer only 3 other users at max.

    CREATE TABLE users
    (
      id serial NOT NULL,
      reference_number SMALLINT NOT NULL,
      CONSTRAINT CHK_reference_number CHECK(reference_number BETWEEN 1 AND 3),
      CONSTRAINT UNQ_reference_number UNIQUE(id, reference_number),
      referred_by integer NOT NULL,
(snip)

Note that your design does not prevent cycles. We can easily enforce that via constraints as well. I can elaborate if you are interested.

Regarding the efficiency of finding qualifying descendants, we can add some redundant data and get much better speed. For example, E is a descendant of A, but not a direct one - B is between them. We can store the following rows:

Ancestor: A
AncestorLevel: 1
Descendant: B
DescendantLevel: 2

Ancestor: B
AncestorLevel: 2
Descendant: E
DescendantLevel: 3

Ancestor: A
AncestorLevel: 1
Descendant: E
DescendantLevel: 3

Once we have this redundant data, finding descendants is easy and fast - just one simple query without recursion. Naturally, with this approach we need substantially more storage.

Of course, with redundant data there is always the risk that it is inconsistent. We can use constraints to enforce the integrity of redundant data. This is complex but doable.