nik*_*uru 7 index optimization
SELECT A
FROM T
WHERE M > 1000 AND M < 5000;
我无法判断以下哪个最适合上述查询：
哪个是最佳答案，为什么？
我最近在考试中遇到了这个问题，但找不到解决方案。我选择了选项 3（在 M 上有索引的 B+ 树），因为查询不是在 M 上排序的，并且与 M 相比，A 上的 B+ 树索引会使其变得困难（我猜）。
我想对这些概念进行一些澄清，因为我对何时可以有效地使用上述每个概念感到有些困惑。
更清楚一点：当查询优化器选择优化计划时，它会选择哪个给定选项？这就是问题的意图。
让我们考虑一个具有 N 个项目的数据集，其中 P 个项目与谓词匹配并将由查询返回。
1a.线性搜索，未排序的数据。在读取该值之前，算法无法知道该值是否与谓词匹配。因此唯一的解决方案是读取所有值并忽略那些与谓词不匹配的值。努力将是 O(N)。
1b. 线性搜索，数据按 M 排序。在这种情况下，我们确保与谓词匹配的所有值在数据中都是连续的。但是，无法知道第一个值的偏移量，因此，从头开始读取是唯一的方法。一旦读取的值大于上限，算法就可以停止。因此，总的来说，这种方法比未排序的方法要快。然而，它仍然是 O(N)。
2.M 上的二分搜索。二分搜索需要对数据进行排序。找到下/上边界将需要更少的操作——它是一个 O(log N) 算法。然而，读取下限和上限之间的所有值是 O(P)，所以总的来说这是查询的复杂性。
3. M 上的 BTree 索引。在这种情况下，BTree 是二分搜索的更一般形式。两者都通过在算法的每次迭代中消除一小部分可能的结果来进行操作。这个部分被称为扇出。对于二进制搜索，扇出为 2，即每次迭代后保留的值的 1/2。对于 BTree，扇出由数据页上可以保存的索引行数决定，该数通常远大于 2，因此可以在更少的迭代中找到特定值。然而，复杂性是相同的，在 O(log N) 处找到下限，在 O(P) 处读取值。
当查询优化器选择优化计划时，它将选择哪个给定选项
它会选择最便宜的。优化器的工作是检查查询的各种物理实现（使用和索引、扫描所有行、对数据进行排序等），应用启发式为每个排列分配成本并提供最便宜的（就估计经过的时间而言）到执行引擎作为查询计划。请注意，在 Big-O 术语中，最便宜的不一定是最不复杂的。Big-O 表示法显示了当项目数量接近一个非常大的限制时所需的工作量如何变化。然而，大多数数据库没有无限多的行。优化器具有有关数据集中值的实际数量和分布的信息。这些存储在内部统计对象中。
让我们举一个例子，我们在 M 上有一个 BTree，它有 3 层深。整个表在磁盘上占用 1,000 页。请记住，所有数据移动一次一页。如果给定的查询可能只返回单行，那么使用 M 上的索引来读取总共四页（3 来自 M 上的索引，1 来自表以获取 A 的相应值）将是有效的。另一方面，如果统计数据表明大部分数据页将被读取，则将索引纳入索引并扫描所有数据页，忽略与谓词不匹配的数据页会更有效。
我从未听说过在 DBMS 中实现的二分搜索。BTrees 以更高的性能提供相同的功能。
当不存在索引或使用索引的开销大于识别单个行的好处时，将使用线性搜索（也称为表扫描）。
BTree 不是唯一的索引类型。单值查找和表扫描不是唯一可能的算法。