我正在寻找一种为矩形提供索引的数据结构。我需要插入算法尽可能快，因为矩形将在屏幕上移动（考虑用鼠标将矩形拖动到新位置）。
我研究过 R-Trees、R+Trees、kD-Trees、Quad-Trees 和 B-Trees，但据我了解，插入通常很慢。我更喜欢以亚线性时间复杂度插入，所以也许有人可以证明我对列出的任何一个数据结构都错了。
我应该能够查询数据结构，以了解哪些矩形在点（x，y）或哪些矩形与矩形相交（x，y，宽度，高度）。
编辑：我想要插入这么快的原因是因为如果你想到一个矩形在屏幕上移动，它们将不得不被删除然后重新插入。
谢谢！
我会使用多尺度网格方法（相当于某种形式的四叉树）。
我假设您使用的是整数坐标（即像素）并且有足够的空间来容纳所有像素。
有一个矩形列表数组，每个像素一个。然后，将 2×2 分箱，然后再做一次。一次又一次，一次又一次，直到你有一个像素覆盖一切。
现在，关键是您将矩形插入到与矩形大小非常匹配的级别。这将类似于 (pixel size) ~= min(height,width)/2。现在，对于每个矩形，您只需要在列表中进行少量插入操作（您可以在上面用一个常量将其绑定，例如选择具有 4 到 16 个像素之间的东西）。
如果要在 x,y 处查找所有矩形，请查看最小像素列表，然后查看包含它的 2x2 合并像素列表，然后查看 4x4 等；你应该有 log2(# of pixel) 步骤来查看。（对于较大的像素，您必须检查 (x,y) 是否真的在矩形中；您希望大约一半的像素在边界上成功，并且所有像素都在矩形内成功，所以您会期望不比直接查找像素多 2 倍的工作量。）
现在，插入呢？这非常便宜——O(1) 就可以将自己排在列表的前面。
删除呢？那更贵；您必须查看并修复您输入的每个像素的每个列表。在空间中该位置重叠且大小大致相同的矩形数量中，这大约是 O(n)。如果您有大量的矩形，那么您应该使用其他一些数据结构来保存它们（散列集、RB 树等）。
（请注意，如果您的最小矩形必须大于一个像素，则您不需要实际形成一直到像素级别的多尺度结构；只需向下直到最小的矩形不会在您的合并像素内无可救药地丢失.)
这可能是一个扩展的评论，而不是一个答案。
我对你真正想要什么感到有点困惑。我猜你想要一个数据结构来支持快速回答诸如“给定矩形的 ID，返回其当前坐标”之类的问题。是对的吗 ？
或者你想回答'什么矩形在位置（x，y）'？在这种情况下，尺寸与显示器的高度和宽度匹配的数组可能就足够了，数组中的每个元素都是该像素上的矩形列表（可能很短）。
但是随后您声明您需要一种插入算法以尽可能快地处理不断移动的矩形。如果你在屏幕上只有 10 个矩形，你可以简单地拥有一个包含每个矩形坐标的 10 元素数组。更新它们的位置将不需要任何插入到数据结构中。
有多少个长方形？它们的创建速度有多快？并摧毁？你想如何处理重叠？矩形只是一个边界，还是包括内部？
您提到的数据结构非常复杂：特别是 B-Trees 应该很快（插入成本随着存在的项目数量的对数增长）但不会加快您的交集查询。
忽略这一点 - 并希望最好 - 空间数据结构分为两部分。第一部分告诉您如何从数据中构建树形结构。第二部分告诉您如何跟踪每个节点上描述存储在该节点下的项目的信息，以及如何使用它来加快查询速度。
您通常可以捏造关于在每个节点上跟踪信息的想法，而无需使用关于应该如何构建树的（昂贵的）想法。例如，您可以通过位交织点的坐标为每个矩形创建一个键，然后使用完全普通的树结构（例如 B 树或 AVL 树或红黑树）来存储它，同时仍然在每个节点上保留信息。在实践中，这可能会加快您的查询速度——尽管在您实施并在真实数据上进行测试之前，您无法判断这一点。大多数方案中的树构建指令的目的是提供性能保证。
两个后记：
1) 我喜欢 Patricia 树 - 它们相当容易实现，添加或删除条目不会过多地干扰树结构，因此您无需太多工作来更新存储在节点上的信息。
2) 上次我查看窗口系统时，它根本不关心任何这些聪明的东西——它只是保留一个线性项目列表，并在需要时一直搜索它：这已经足够快了。