Question

数据库索引为什么会提高查询速度？

谁帮忙解释一下原理，不要说什么像书的目录，我很不理解，书的目录对人是有作用，因为目录排的比较紧密，人是思想动物，人可以一目十行，快速找到对应的页码，但是计算机有什么作用？计算机查找某一条记录，如果不加索引，会在整个表中一条一条比较，将匹配的记录加入结果集，很多人说这样会很慢，加了索引就快了，说什么，计算机先在索引列表中找到记录的位置，既rowid，然后直接去表中的对应位置取出记录，我就不明白了，查找索引列表难道不需要一条一条的匹配？计算机又不会出现说，看索引列表比直接看表中的记录要快，先在索引列表中找到记录对应的rowid也是要遍历的？难道不是同样的吗？顶多说索引列表是排好序的，可以通过类似于二分查找快速找到。难道还有其他什么机密吗？希望高人详细解释一下，为什么有索引会快很多倍

Answer 1

你的理解其实没啥问题。索引就是通过事先排好序，从而在查找时可以应用二分查找等高效率的算法。
一般的顺序查找，复杂度为O(n)，而二分查找复杂度为O(log2n)。当n很大时，二者的效率相差及其悬殊。

举个例子：
表中有一百万条数据，需要在其中寻找一条特定id的数据。如果顺序查找，平均需要查找50万条数据。而用二分法，至多不超过20次就能找到。二者的效率差了2.5万倍！

Answer 2

首先是建立在内存上。且一般只有数字主键时快的明显一些。

Answer 3

比如说 一本书 你要查 一段数据 你是 去把整本书翻一遍 快呢 还是 从目录开始找 快呢 ，索引就是这个 目录了。