How does that help here? My query doesn't contain any directly-searchable strings, unless you start abstracting things by treating all alpha chars as the same, etc.
Say your query is \d+(th|nd|rd), and your searchable text is "The 3rd planet from the sun is 20000000 miles away." Your tree search will hit 2, then fail on 20, then 3, then 3r, then 3rd, and then terminate successfully. So we followed 5 pointers, and tested another 20 or so for nullity.
This was independent of the length of the searchable text (but not the number of found matches). It would have performed equally well on "The 3rd planet from the sun is 20000000 miles away. Lorem ipsum (insert 10mb of random Latin here)".
Assuming their claim of 116,000,000 matches for /./, and 5k mean document size, 70TB, uncompressed.
Papers like "Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching" [1] lead me to believe that the state of the art could be as low as 4 bits/char, in which case the answer would be a much more tractable 270GB.
As far as partitioning goes, now I'm getting really out of my league. At a first pass, I imagine that you could keep the root and neighbors on a primary server, and as big of subtrees as you can fit in RAM on a bunch of slaves. The first couple chars get processed in the master, and then however many subtrees are alive get delegated in parallel to the secondary servers. The secondary servers return the answers to the primary, which returns to the client.
I feel like I'm answering hypothetical questions at a job interview :p
5800 machines is practical for a real product. Hardware probably costs Google $40/month/CPU, so $230k / month, about equal to 10 engineers. So if a more clever solution needs a whole team to maintain it then it's probably better to just use grep.