Nic*_*rey 27
大多数关系数据库将索引结构化为B树.
如果表具有聚类索引,则将数据页存储为B树的叶节点.本质上,聚类索引成为表.
对于没有聚类索引的表,表的数据页存储在堆中.任何非聚集索引都是B树,其中B树的叶节点标识堆中的特定页面.
B树的最坏情况高度是O(log n),并且由于搜索取决于高度,因此B树查找的运行方式类似于(平均而言)
O(log t n)
其中t是最小化因子(每个节点必须至少有t -1个键,最多2*t*-1个键(例如,2*t*个子).
这就是我理解它的方式.
当然,不同的数据库系统可能会使用不同的数据结构.
当然,如果查询不使用索引,则搜索是对包含数据页的堆或B树的迭代.
如果使用的索引可以满足查询,则搜索会便宜一些; 否则,需要在内存中获取相应的数据页.
索引查询（唯一查询或非唯一查询）通常为O（log n）。非常简单地说，您可以认为它类似于排序数组中的二进制搜索。更准确地说，它取决于索引类型。但是，例如，b树搜索仍然是O（log n）。
如果没有索引，则为O（N）。
如果您选择搜索的相同列，则
如果您需要来自另一个“源”（索引交集、书签/键查找等）的信息，因为索引是非覆盖的，那么您可能有 O(n + log n) 或 O(log n + log n + log n)因为多个索引命中+中间排序。
如果统计数据显示您需要高百分比的行（例如，不是非常有选择性的索引），那么该索引可能会被忽略并变为扫描 = O(n)