I don't know how [vi] avoids the lack of a terminfo database, though.

I suspect it has a basic one compiled in. I've had a few problems with it. For instance, no matter how big my window is when I start vi, it only uses 25 lines. No biggy... still better than the alternative...