Field pattern queries over key-value API records

API records are strings like method=get;path=users. Answer many queries of the form key=pattern, each true when some record has that key with a matching value. A pattern is an exact value, a prefix followed by *, or * alone for any value. Matching is case-sensitive.

Parse the records once and build an index so each query looks only at the values stored under its key; prefix queries should not scan every value either. Discuss the trade-off between a sorted list with binary search and a trie per key.