Indexing and searching a bit-accurate trace for arbitrary length/arbitrary alignment values in traced thread(s). Indexing includes, while replaying a plurality of trace segments, identifying a set of n-grams for each trace segment that exist in processor data influx(es) and/or store(s) to a processor cache that resulted from replay of the trace segment. An index data structure, which associates each identified n-gram with trace location(s) at or in which the n-gram was found, is then generated. The index data structure thus associates unique n-grams with prior execution time(s) at or during which the traced thread(s) read or wrote the n-gram. Searching an indexed trace includes identifying n-grams in a query and using the index data structure to determine trace location(s) where these n-grams were seen during indexing. A query response is generated after using trace replay to locate particular execution time(s) and memory location(s) at which the n-grams occurred.