Yes, someone needs to have a lookup table from prevouts to TXO tree positions. But because an insertion-ordered TXO tree does not rebalance, that table can be maintained by wallets or service providers for just their own coins, instead of by every full node and miner individually for everyone's coins.