总结：
- 数据库存储顺序随机，如果没有索引，每次查询都需要一行行遍历，查找出符合条件的点，复杂度 O(N)
- 数据库会按照 rowid 排序，并给主键建立索引，所以如果以 rowid 或者主键为搜索条件，复杂度可以近似看做二分查找的复杂度，即 O(logN)
- 如果没有主键，或搜索条件不是主键，可以给搜索目标增加索引，将该字段的搜索复杂度，提升到 O(logN)
- 如果搜索条件有多个，可以建立组合索引 (multi-column index)，将搜索复杂度，降低到 O(k * logN)
- 注意，如果搜索条件中带有范围的搜索，可能导致索引失效，退化到 O(N) 复杂度，可以通过合理排列联合索引的字段顺序来避免。
https://blog.tankery.me/development/why-we-need-indexes-for-database
标签：为什么,数据库,索引,搜索,复杂度,logN,主键 From： https://www.cnblogs.com/zhangcheng2020/p/17719148.html