在削减的情况下，研究了如何安排一个好的多维索引算法的问题。 令人惊讶的是，没有太多选择。
一维指数，B树
搜索算法成功的衡量标准将被视为2个事实-
- 确定存在或不存在结果的事实的事实是对数（相对于索引大小）的磁盘页读取次数
- 发布结果的成本与其数量成正比
从这个意义上说，B树非常成功，其原因可以被认为是平衡树的使用。 该算法的简单性归因于键空间的一维性-如有必要，可以拆分页面，将该页面元素的排序集合拆分为一半就足够了。 通常不必除以元素数，但这不是必需的。
因为 树的页面存储在磁盘上，可以说B树具有将一维密钥空间非常有效地转换为一维磁盘空间的能力。
当用或多或少的“正确插入”填充一棵树时，这是一种很常见的情况，页面是按键的增长顺序生成的，偶尔会与较高的页面交替出现。 它们也很有可能也位于磁盘上。 因此，无需任何努力，就可以实现较高的数据局部性-价值不高的数据将位于附近且在磁盘上。
当然，以随机顺序插入值时，键和页面是随机生成的，因此，所谓的 索引碎片。 还有一些防碎片整理工具可以恢复数据的局部性。
在我们的RAID和SSD磁盘时代，从磁盘读取的顺序似乎无关紧要。 但是，它的含义与以前不同。 SSD中没有磁头的物理转发，因此与诸如HDD的固态读取相比，其随机读取速度不会降低数百倍。 而且每10个或
更多一次。
回想一下，B树在磁带和鼓的时代出现于1970年。 与HDD和SSD相比，上述磁带和鼓的随机访问速度差异要大得多。
另外，十倍也很重要。 这10次不仅包括SSD的物理功能，还包括基本点-读取器行为的可预测性。 如果读者很有可能要求该块的下一个块，则可以通过假设主动下载它。 如果行为混乱，那么所有的预测尝试都是毫无意义的，甚至是有害的。
多维索引
进一步，我们将处理二维点（X，Y）的索引，只是因为使用它们方便且直观。 但是问题基本相同。
根据我们的成功标准，带有X和Y分别索引的简单“简单”选项不会通过。 它没有给出获得第一点的对数成本。 实际上，要回答这个问题，在期望范围内是否有任何东西，我们必须
- 在索引X中进行搜索，并从X间隔范围中获取所有标识符
- 与Y类似
- 与这两套标识符相交
第一项已经取决于范围的大小，并且不能保证对数。
为了“成功”，多维索引必须安排为或多或少平衡的树。 这个说法似乎有争议。 但是对数搜索的要求对我们来说就是这样一种设备。 为什么没有两棵或更多棵树？ 已经考虑了两棵树的“简单性”和不合适的选择。 也许有合适的。 但是有两棵树-这是两倍（包括同时）锁，成本是两倍，因此，遇到死锁的机会也要大得多。 如果您能与一棵树打交道，则一定要使用它。
考虑到所有这些，将非常成功的B树经验作为基础并“概括”它以使用二维数据的愿望是很自然的。
于是出现了R树。
R树
R树的安排如下：
最初，我们有一个空白页，只需向其添加数据（点）。
但是这里页面已满，需要拆分。
在B树中，页面元素以自然的方式排序，因此问题是要削减多少。 R树中没有自然顺序。 有两种选择：
- 带来秩序，即 引入一个基于X＆Y的函数，该函数将根据页面元素的排序和分配给出一个值。 在这种情况下，整个索引会退化为根据指定函数的值构造的规则B树。 除了明显的优点外，还有一个大问题-好吧，好吧，我们将其编入索引，但外观如何？ 稍后，请首先考虑第二个选项。
- 按空间标准划分页面。 为此，应为每个页面分配位于其上/下方的元素的范围。 即 根页面具有整个图层的范围。 拆分时，将生成两个（或更多）页面，其范围包括在父页面的范围内（用于搜索）。
充满不确定性。 如何精确分割页面？ 水平还是垂直？ 从一半面积还是一半元素开始？ 但是，如果这些点形成了两个簇，但是您只能用对角线将它们分开，该怎么办？ 如果有三个集群？
仅存在此类问题表明R树不是一种算法。 这是一组试探法，至少用于在插入过程中拆分页面，在删除/修改过程中合并页面，用于批量插入的预处理。
启发式方法涉及特定树在特定数据类型上的特殊化。 即 在某种数据集上，她犯错的频率降低了。 “启发论不能完全误解，因为 在这种情况下，它将是一种算法“©。
在这种情况下，启发式错误是什么意思？ 例如，页面将被分割/合并失败，并且页面将开始部分重叠。 如果突然搜索范围落在页面的重叠区域上，则搜索成本将不是很对数。 随着时间的流逝，随着您插入/删除错误的次数不断累积，树的性能开始下降。
图1这是以自然方式构建的R *树的示例。
图2在这里，相同的数据集已经过预处理，并且通过大量插入构建了树我们可以说B树也会随着时间而退化，但这是一个稍微不同的退化。 由于B页的页面不连续，B树的性能下降。 可以通过“拉直”树的碎片整理来轻松处理。 对于R树，摆脱它不是那么容易；树本身的结构是“曲线”以纠正这种情况；
R树到多维空间的一般化并不明显。 例如，在拆分页面时，我们最小化了子页面的边界。 在三维情况下应最小化什么？ 体积或表面积？ 在八维情况下呢？ 常识不再是顾问。
索引空间很可能是非各向同性的。 为什么不只索引点，还索引它们在时间上的位置，即 （X，Y，t）。 在这种情况下，例如，基于周长的启发式是没有意义的，因为 以时间间隔堆叠长度。
R树的一般印象是
g足甲壳类动物。 那些有自己的生态位，很难与它们竞争。 但是在一般情况下，它们没有机会与更发达的动物竞争。
四叉树
在
四叉树中，每个非叶子页面都有正好四个后代，这些后代将其空间平均划分为多个象限。
图3构造的四叉树示例这不是一个好的数据库设计。
- 每个页面仅缩小两次每个坐标的搜索空间。 是的，这提供了搜索的对数复杂度，但这是2的对数，而不是B树中页面上元素的数量（甚至100）。
- 每个页面都很小，但是在它后面您仍然必须转到磁盘。
- 必须限制四叉树的深度，否则其不平衡会影响性能。 结果，在高度聚集的数据上（例如，地图上的房屋-城市中有很多城市，田野中很少），大量数据可以累积在页面上。 精确索引的索引变得块状，需要进行后处理。
选择不当的晶格大小（树深度）可能会降低性能。 不过，我希望算法的性能不严格取决于人为因素。
- 存储一个点的空间成本相当大。
空间编号
仍然需要考虑以前的延迟版本，该版本具有一个功能，该功能可以在多维键的基础上计算要在常规B树中写入的值。
这样的索引的构造是显而易见的，并且索引本身具有B树的所有优点。 唯一的问题是该索引是否可以用于有效搜索。
这样的功能有很多，可以假设其中有少量的“好”，大量的“坏”和大量的“糟糕”。
找到一个可怕的函数并不困难-我们将密钥序列化为字符串，从中考虑MD5并获得一个对我们的目的完全无用的值。
以及如何对待善良？ 已经有人说过，有用的索引可以提供数据的“局部性”，即空间上很近的点，在保存到磁盘时通常彼此靠近。 当应用于所需功能时，这意味着对于空间上的接近点，它将给出接近的值。
进入索引后，计算出的值将按其值的顺序显示在“物理”页面上。 从“物理意义”上看，搜索范围应该影响尽可能少的物理索引页。 通常很明显。 从这个角度来看，“拉”数据的编号曲线是“不良”的。 而那些“混淆不清”的人-接近“好”。
天真的编号
尝试将片段压缩为正方形（超立方体），同时保留一维空间的逻辑，即 切成碎片，并用这些碎片填充正方形。 可能是
4线扫描
5隔行
图6螺旋或...您可以想出很多选择，它们都有两个缺点
- 例如，模糊性：为什么螺旋是顺时针卷曲而不是不卷曲，或者为什么水平扫描首先沿X然后沿Y
- 长直件的存在使使用这种方法对多维索引无效（大页面周长）
直接访问功能
如果“天真的”方法的主要主张是它们生成了很长的页面，那么让我们自己生成“正确的”页面。
这个想法很简单-让外部将空间划分为多个块，为每个块分配一个标识符，这将成为空间索引的关键。
- 让X＆Y坐标为16位（为清楚起见）
- 我们将使用尺寸为1024X1024的正方形块覆盖空间
- 粗化坐标，向右移动10位
- 并获取页面ID，粘贴X＆Y中的位。 现在在标识符中，低6位是X的最旧数字，接下来的6位是Y的最旧数字
很容易看到这些块形成了行扫描，因此，要查找搜索范围的数据，您将必须对该范围所在的每一行块的索引进行搜索/读取。 通常，此方法虽然有几个缺点，但效果很好。
- 创建索引时，您必须选择最佳块大小，这完全不明显
- 如果该数据块比典型查询大得多，则搜索将效率低下，因为 必须阅读和过滤（后处理）太多
- 如果该数据块明显小于典型查询，则搜索将效率低下，因为 将不得不逐行执行很多查询
- 如果该块平均数据过多或过少，则搜索将无效
- 如果数据是聚类的（例如：在地图上的首页），搜索将不会在所有地方都有效
- 如果数据集增加了，很可能证明块大小不再是最佳的。
通过构建多层模块可以部分解决这些问题。 对于同一示例：
- 仍然需要1024X1024块
- 但现在我们仍然有大小为8X8的较低块的顶级块
- 键的安排如下（从低到高）：
3位-10 ... 12 X坐标
3位-10 ... 12 Y坐标
3位-13 ... 15 X坐标
3位数-13到15位Y坐标
7个低级块构成高级块现在，在很大程度上，您不需要读取大量的小块，这是以牺牲高级块为代价的。
有趣的是，可能不对坐标进行粗化，而是以相同的方式将其压缩到关键点中。 在这种情况下，后过滤会更便宜，因为 读取索引时会发生。
空间
GRID索引以类似的方式
在MS SQL中进行排列；其中最多允许4个块级别。
图8 GRID索引直接索引的另一种有趣的方式是使用四叉树对空间进行外部分区。
四叉树很有用，因为它可以适应对象的密度，因为 当节点溢出时，它会分裂。 结果，在对象密度高的地方，块会变小，反之亦然。 这减少了空索引调用的数量。
的确，四叉树是一种不方便即时重建的构造，因此不时进行此操作是有利的。
令人高兴的是，当重建四叉树时，如果通过
莫顿代码标识块并且使用该对象编码对象，则无需重建索引。 诀窍是：如果点的坐标是用莫顿码编码的，则页面标识符是该代码中的前缀。 搜索页面数据时，选择从[prefix] 00 ... 00B到[prefix] 11 ... 11B范围内的所有键，如果页面被拆分，则意味着仅其后代的前缀已加长。
自相似特征
提到自相似函数时，首先想到的是“扫描曲线”。 “引人注目的曲线是连续映射，其范围是单位段[0，1]，范围是欧几里德（更严格地讲，拓扑）空间。”
皮亚诺曲线就是一个例子
。
图9 Peano曲线的第一次迭代左下角是定义区域的开始（以及函数的零值），右上角是结束区域（和1），每当我们移动1步时，将值加1 /（N * N）（假设N-当然是3级）。 结果，该值在右上角达到1。如果我们在每一步加一个，则此函数只需按顺序编号方格，这就是我们想要的。
所有扫描曲线都是自相似的。 在这种情况下，单纯形是一个3x3的正方形，在每次迭代中，单纯形的每个点都变成同一个单纯形，为确保连续性，您必须求助于映射（翻转）。
自我相似对我们来说是非常重要的素质。 它为搜索的对数值提供了希望。 例如，对于一个3x3的单纯形，在9个基本平方的每个内通过后续详细信息迭代生成的所有数字都将在同一范围内。 仅因为数字是从头开始走过的路。 即 如果将范围划分为9个部分，则可以通过一个索引遍历获得每个部分的内容。 依此类推，可以通过对索引的一次查询来获得每个正方形的9个子正方形（尽管范围较小）。 因此，搜索范围可以分解为少量的正方形子查询，可以整体读取或通过过滤（围绕周边）进行读取。 图9以绿色显示搜索范围，用红色线将其分成子查询。
但是，自相似性不会自动使编号曲线适合于索引目的。
- 曲线应填充正方形网格。 我们为方格的节点中的值编制索引，并且每次我们不想在格上寻找合适的节点时，例如三角形。 至少是为了避免舍入问题。 例如，在这里（图10）
图10 Kokha三元湖
曲线不适合我们。 虽然如此，它完美地“桥接”了表面。
- 曲线应填充无间隙的空间（ 分形维数 D = 2）。 这是 （图11）：
11.匿名分形曲线
也不合适。
- 编号函数的值（从起点开始沿曲线行进的路径）应易于计算。 由此得出的结论是，由于产生歧义，自触曲线不适合使用，如谢尔宾斯基曲线
图12 Sierpinski曲线
或者（对于我们而言）是相同的，“ 沿Cesaro传递三角形 ”
图 13 Cesaro三角形，为清楚起见，将直角替换为85° - 编号函数中不应有参数，曲线应均匀（准确对称）。 . : ( )
. 14 “A Plane Filling Curve for the Year 2017”
, ( ) .
, , , .
各向同性是另一个重要特征。可以理解，编号功能应易于推广到更高的尺寸。如果对一个N维立方体来说，它在尺寸（N-1）上的所有N个投影都相同，则是很好的。这是由于我们使用了各向同性空间这一事实，如果不同的轴在函数中使用的方式不同，这将很奇怪。
图15 3x3x3 Peano曲线的三维单纯形不是严格的要求，但它是编号曲线质量的重要指标。关于连续性。上面，我们看到了不适合我们目的的连续编号函数的示例。另一方面，带有块的不连续的行扫描功能对此非常有用（有一些限制）。不仅如此，如果我们基于连续的隔行扫描构建块索引，那么就性能而言不会有任何改变。因为如果整个读取块，则接收对象的顺序没有区别。对于自相似曲线也是如此。- 我们称页面大小为磁盘页面上所有对象的扩展区域
- 特征尺寸将是平均页面面积
- ( ) , . , . — . .
- — , .. .
- , . , , . , , — () 3...10% () Z-.
— , .
, () , ( ) .
, , - , . , , . ,
.
.
, ? .
().
, , . , . , 3X3 3 X, 3 Y. . () 5X5, 5 . (ex: 2+3), .
- — , 5- 7- , .
有自己的狭窄位置，可以按前缀搜索。这并不是直觉上理解为三元树的东西。这可以通过效率来解释。在三元节点中，要选择后代，必须进行2次比较。在二叉树中，这对应于4个选项中的一个。甚至更短的树深度也不会阻止比较次数的增加而导致生产力下降。另外，如果3X3比2X2更有效，仅仅是因为3> 2，则4X4会比3X3更有效，而8X8会比5X5更有效。您总是可以找到适当的2的幂，它由2X2的多次迭代形成... 单形旁路对什么有影响？首先，是搜索生成的子查询数。因为 , . 3X3 , 3 . 8x8 (.16), — 64 .
. 16 8x8, , 2x2, , .
. 17 2x2, , , “Z”, “” “”.
, “” , . 4 . 256 8- .
对不同尺寸的空间使用单一算法的能力（在像“ alpha”这样的曲线的情况下我们将其剥夺）看起来很有吸引力。因此，将来我们将仅考虑前两个选项。
图 图18的Z曲线
。19“ omega”-希尔伯特曲线，一旦这些曲线具有近亲关系，就可以用一种算法对其进行处理。曲线的主要特异性位于子查询的拆分中。- 首先，我们找到起始范围，这是包含搜索范围并包含一个连续键值间隔的最小矩形。
发现如下-
- 计算搜索范围的左下角和右上角的关键值（KMin，KMax）
- ( ) KMin, KMax
- , SMin, , SMax
- . , , SMin, . .
- , , ( ).
- Z- . z- — , — ( ). , , .
- , , . ,
- , . — “ ” >= “ ” () , “ ”
- “ ” > , ,
- , ,
- “ ” > , , ,
- 单独的大小写“ last key” ==当前子查询的最大值，由遍历向前处理
- 拆分当前子查询
- 在其前缀上添加0和1-我们得到两个新的前缀
- 填写键0或1的其余部分-我们获得新子查询的最小值和最大值
- 我们将它们压入堆栈，首先将其加1，然后再加0。这是用于单向读取索引。
在Z曲线上，它的工作方式如下：
图 20-Z曲线情况下的子查询拆分
图 21 Hilbert曲线，起始程度最大时此处显示了第一阶段-从最大范围中切除多余的图层。
图 22希尔伯特曲线，搜索查询区域以下是搜索查询区域中子查询，找到的点和索引调用的细分。 从希尔伯特曲线的角度来看，这仍然是一个非常不成功的要求。 通常，一切都没有那么多血腥。
但是，查询统计数据表明（大致）在相同数据上，基于希尔伯特曲线的二维索引平均读取的磁盘页面减少了5％，但运行速度慢了一半。 速度下降的原因还在于，此曲线的计算本身（正向和反向）更加困难-Hilbert为2000个处理器周期，而Z曲线为50个处理器周期。
通过停止支持希尔伯特曲线，可以简化算法；乍看之下，这种放慢是没有道理的。 另一方面，这只是二维情况，例如，在8维或更多的空间中，统计信息可能会以全新的颜色闪烁。 这个问题仍在等待澄清。
PS ：Z曲线有时被称为位交织曲线，因为该算法用于计算值-每个坐标的数字都通过一个落入关键值，这是非常技术性的。 但是，毕竟，您可以不逐个交错放电，而是以2.3 ... 8 ...的包装进行交错。 现在，如果我们使用8位，则在32位密钥上，我们从MS SQL获得了4级GRID索引的类似物。 在极端情况下-每包32位-一种水平扫描算法。
这样的索引（当然不是小写）可能非常有效，甚至比某些数据集上的Z曲线更有效。 不幸的是，由于失去普遍性。
PPS ：描述的索引与使用四叉树非常相似。 最大范围是四叉树的根页，它有4个后代...因此，该算法可归因于“直接访问方法”。
差异仍然是根本。
四叉树没有存储在任何地方，它是虚拟的，嵌入在数字的本质中。 树的深度没有限制；我们从主树的种群中获取有关后代种群的信息。 而且，主树只被读取一次，我们从最小到最大。 这很有趣，但是B树的物理结构可以避免空查询并限制递归深度。
还有一件事-每次迭代仅出现两个子代-从中可以生成4个子查询，如果它们下没有数据，则不能生成。 在3维情况下，我们将讨论8个后代，在8维情况下-大约256个。
PPPS ：在本文的开头，我们讨论了在多维索引中进行搜索时的二分法-为了获得对数值，有必要在每次迭代时分配一些有限的资源-键值空间或搜索空间。 在提出的算法中，这种二分法崩溃了-我们同时共享密钥和空间。
“我住在两个院子里，我的树总是更高。”（
C ）
PPPPS ：一旦他们调用Z曲线，就在这里有了Z阶和位交织以及Morton码/曲线。 它也被称为勒贝格曲线，因此为了保持平衡，作者以包括
亨利·莱昂·勒贝格的荣誉为标题。
PPPPPS ：在标题插图中，
Fedchenko冰川的景色很美，而且有足够的空虚度。 实际上，不同的思想和方法如何顺畅地相互融合，并逐渐融合为一种算法，给作者留下了深刻的印象。 正如组成流域的许多小水源形成一个径流一样。