Embodiments are directed to a searchable encryption model for fast indexing and searching of encoded documents. The encoded documents may have multiple encryption and/or compression layers applied. The model supports full or partial keywords and simple or complex queries. The index model may be based on prefix trees to optimize space and time complexities during indexing and searching. This index model can be used as the foundation to more complex search engines. Indexed documents may be tokenized and each token indexed in a prefix tree data structure, or trie index. Tokens in the index may be associated with a token catalog that includes information related to the documents that include the token. Token catalogs may be implemented as inverted indices that map tokens to documents. If a query is provided, a result set responsive to the query may be provided based on the token index and the token catalogs.