Documents and search terms may be received for which an index that supports both incremental document indexing and incremental term indexing is to be generated. From this information, an index may be generated, partitioned in a first dimension by documents to create master segments and in a second dimension by search terms to create slave segments. A request to update the index to include a new document or a new search term may be received. The new document or new search term may be added to the index without modifying the entire index. Further, document identifiers may be synchronized across all segments. Synchronization refers to maintaining consistency of document identifiers across segments, despite renumbering of document identifiers during certain operations such as merging segments.