Elasticsearch insert(Post)写入请求的时间复杂度是多少？

首先澄清一个前提偏差：你提到的Get查询O(1)复杂度，仅针对按文档ID做精确查询的场景——这类请求不需要遍历倒排索引，直接通过文档ID定位内存缓冲区、Translog里的文档记录即可，复杂度确实接近O(1)。如果是带条件的全文检索、聚合查询，需要遍历倒排链做集合运算、聚合计算，复杂度远高于O(1)。

回到写入请求的复杂度问题，ES是基于Lucene的近实时搜索引擎，写入流程分两个核心阶段，复杂度完全不同：

• 即时响应阶段（客户端收到写入成功响应的阶段）
  写入请求路由到目标分片后，只会做两个操作：一是把文档写入内存的Index Buffer，二是顺序追加写入Translog事务日志做故障兜底。这两个操作都没有复杂的索引构建逻辑，属于顺序写+内存操作，这个阶段的时间复杂度是O(1)，耗时仅和单条文档的字段长度、分词复杂度相关，和集群已有的总数据量没有关系。
• 可检索准备阶段（文档真正进入倒排索引的阶段）
  ES默认每隔1秒（可通过参数index.refresh_interval调整）会把内存缓冲区攒的一批数据生成一个新的不可变Lucene段（Segment），这个过程会为这批新文档构建独立的倒排索引。单批次构建倒排的时间复杂度是O(n)，这里的n是当前批次所有文档分词后产生的Token总数量，不是集群全量数据规模，所以这个阶段的耗时不会随集群总数据量上涨线性升高。

额外说明：Lucene后台会定期执行段合并，把多个小段合并成大段来减少查询时的段遍历开销，这个过程是异步执行的，不会阻塞前端写入请求，只会占用后台的CPU、磁盘IO资源，合并的复杂度和被合并段的总Token量正相关。

很多人误以为写入倒排索引需要修改全量索引所以复杂度很高，实际上Lucene的段是完全不可变的，新写入的数据只会生成新段，永远不会修改已经落盘的旧段，所以不会出现写入性能随数据量增长线性下跌的情况。

内容的提问来源于stack exchange，提问作者qtcat