索引如何帮助基于特定条件搜索数据的速度?
如果有一个包含6个列且没有任何索引的表,则程序必须检查所有表行。
索引涉及创建另一个仅具有两个列(id和所需索引的列)的单独表。
我不理解的是,这如何帮助应用程序进行更快的搜索?它没有读取整个6个列的表,但它仍然必须读取整个2列的表,对吧?其行数相同...
它的功能类似于书中的索引。我们不需要读完整个索引来查找想要的条目,一旦找到条目,我们就不需要继续读取索引以查找该条目的其他实例。一旦找到条目,我们就无需阅读整本书,只需跳转到我们想要的条目。这些操作在正常的表查找和索引中发挥作用,索引可以节省我们时间,就像书中的索引一样。
创建索引基本上会创建一个磁盘上的哈希表或者一个磁盘上的搜索树(通常是 B Tree 的某种形式)。
在哈希表中查找一个完全匹配项的时间复杂度是O(1)
,而在有序搜索树中查找一个完全匹配项或最接近的匹配项的时间复杂度是O(log(n))
。
这与扫描整个表的时间复杂度为O(n)
相比形成对比。