We construct an encrypted search index data structure capable of searching large datasets in microseconds. It only reveals the results of the search queries and preserves the privacy of the remaining data. Unlike prior work, we handle efficiently searching dynamically changing data while simultaneously maintaining strong privacy guarantees.