[Dylan16807]

A tree would require the ability to have control flow based on data, or using data as an index. You can't do that while keeping the data secret.

Just to select a single row you have to do something like sum(row_meets_criteria() * row). With row_meets_criteria returning 0 or 1.

[trhway]

for equality predicate you can just use hash based index, for range search the situation is of course worse, yet you can have a somewhat like a partially/probabilistically preserving order hash so that you can produce a number of candidates orders of magnitude less than the whole table scan.

[RobLach]

The mere fact that you did not need to scan the entire db means the data was not securely encrypted in the first place.

[bawolff]

But then you are not using FHE, but something with much weaker security properties.