Core does this by maintaining a redundant hash table of unspent outputs (the output object including script, indexed by tx hash). By adding and removing from this redundant data, these questions are more simply answered. But it introduces not only a large amount of redundant data, but a heavy ordering requirement.