我还没有找到表索引对表操作的算法顺序的影响的明确指示。
我对具体实现的细节不感兴趣；我假设 RDMS 设计人员知道他们在做什么，并且他们已经尽可能提高了效率。
我将把我的讨论限制在单个索引上，我认为额外的索引只是添加了一个额外的维度（即基本过程必须执行多次）。
下面假设每种情况下只有一条记录 - 索引的好处对于多个记录操作大大增强，因为（通常）查找操作需要执行的次数少于正在查找的记录数，因为它们可以在一个范围内检索。
对于未索引的表，我认为操作是：
Step INSERT SELECT DELETE UPDATE
Find the record N/A O(n) O(n) O(n)
Modify the record O(1) N/A O(1) O(1)
OVERALL O(1) O(n) O(n) O(n)
这假设查找记录需要表扫描，但新记录只是简单地放在末尾。
建立索引是一个基于高效排序算法的 O(nlog(n)) 操作。
对于索引表，我相信操作是：
Step INSERT SELECT DELETE UPDATE
Find the record N/A O(log(n)) O(log(n)) O(log(n))
Modify the record O(1) N/A O(1) O(1)
Update the index O(log(n)) N/A O(1) O(1)
OVERALL O(log(n)) O(log(n)) O(log(n)) O(log(n))
这假设现在查找记录是对索引的有序查找操作，更新索引是一个步骤DELETE和UPDATE（因为您已经找到了记录）和一个有序查找INSERT
也就是说，插入变得更糟，但其他一切都变得更好。
这样对吗？
事情比这更复杂。以下是几点考虑因素。
首先，整个讨论假设 B 树或 B+ 树（因此是 o(log(n))）。还有其他类型的索引，例如哈希索引，其访问时间复杂度为 O(1)。您的问题暗示您正在使用“等于”搜索来查找值（例如寻找X=17）。但在这种特殊情况下，如果可能的话，哈希索引是更好的选择。
我确实同意您今天发现的大多数索引都是 B/B+ 树，所以让我们继续这个假设。
您还隐含地表明 a 中始终只有一个结果行SELECT，这很难说是一种代表性情况；很多时候我们一次查找1,000行。但让我们继续假设单个匹配行。
您的下一个假设是搜索始终由索引列完成。这很好，但我只是注意到，DELETE通过某些未索引的列 ing 记录Y结果会更昂贵：您都浪费 O(n) 时间来查找记录，然后支付额外的 O(log(n )) 用于更新索引。
但是让我们继续假设我们只讨论查找索引列的查询。
有些表使用非聚集索引格式（适合您的计算） - 表是一个实体，索引是另一个实体。其他使用聚集索引格式：表行（或者更确切地说是行块，或者更确切地说是行页）实际上存储为聚集索引内的叶子。在这种情况下，您将花费 O(log(n)) 来查找命令中的记录INSERT。对此的优化是在您插入到表末尾的情况下，一个不错的实现将保存指向索引中最后一个记录/页面的指针。（哦，是的，您不应该担心您的记录被INSERT编辑到表格的中间）。
实际上，即使在非聚集表中，记录也可以插入到表的中间；花费更多的搜索时间以避免碎片是有意义的，据我所知，至少有一个实现可以做到这一点。我假设其他人也可能。
从 BTree 中删除/插入索引的平均时间复杂度为 O(1)，但在传播页面合并/拆分的情况下可能会花费 log(n) 次操作。
此外，总是令许多人感到惊讶的事实是，有时表扫描比索引查找更快。对于产生多行的查询尤其如此。事实证明，查找索引会增加开销；与全表扫描相比，开销实际上可能会使总成本更高。对于单行查找，绝大多数索引查找应该比全表扫描更快。
但请考虑以下一般惯例：您用美元支付任何访问磁盘的操作。您需要花费镍币来支付作用于内存数据中的操作。这实际上是数据库磁盘 I/O 优化的核心。如果索引页位于磁盘上，而表页恰好位于内存中，则您为表扫描支付的费用可能会更少。
这就是造成严重破坏的地方：这实际上完全取决于您的工作负载、内存大小和数据集大小。
您是否曾经上过数学课，要求您解决一些复杂的积分？你花了几个小时才解决这个问题，却因为在某处遗漏了一些微小的减号而被扣分？
您是否参加过必须解决一些复杂积分的物理课？教授会扔掉方程的大部分内容，说“这是可以忽略的”，你会扯掉你的头发吗？为什么它可以被忽视？为什么不做其他事情呢？
计算机科学以数学为基础。计算机是基于物理学的。它们是物理对象。它们需要旋转磁盘、访问内存总线、管理数十亿个晶体管……您实际上无法预测会发生什么并将所有这些都放在某个方程式下。
事实可能是，对于某些特定的数据集，你的整个方程并不成立。在其他时候，可能还好。