我还没有找到表索引对表操作的算法顺序的影响的明确指示。
我对具体实现的细节不感兴趣；我假设 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
也就是说，插入变得更糟，但其他一切都变得更好。
这样对吗？