如果行存储索引存储在 b 树数据结构中，那么列存储索引使用什么样的数据结构？

Question

我对常规行存储索引如何存储的理解是一种 b 树数据结构，但我想知道由于列存储索引的不同性质，使用什么类型的底层数据结构？

Answer 1

我们通常认为索引是一种快速查找对给定信息的所有引用的方法。在给定主题的教科书中，我们可以找到提到该主题的所有页面。在给定列值的数据库中，我们可以找到具有该值的所有行。

从这个意义上说，将列存储称为“索引”有点用词不当。它不打算为特定列值的行提供快速查找。相反，它旨在快速提供大型数据集上的聚合结果。因此，它本身就是一种数据格式。列式数据存储，有时也称为分解存储模型 (DSM)，是众所周知且受人尊敬的。许多专有和开源 DBMS 都提供它。

列存储的基本思想是列的值连续存储在磁盘上。然后，该列上的聚合可以有效地从磁盘中提取该列，并且仅提取该列，从而减少必须读取的磁盘块数。此外，由于块中的所有数据值都来自同一域，因此对该块进行压缩可能非常有效，从而进一步减少了所需的块数量。压缩比一般的 ZIP 好得多——可以使用字典、游程长度和增量编码。

出于各种原因，最好在压缩和存储行之前将行分成大组。SQL Server 将这些组称为“行组”，它们由“列段”组成。每个行组包含超过一百万行。构建段时，服务器会提取该列的一些元数据，例如最小值、最大值和（可能）总和。此元数据有时称为区域映射。在运行时，可以将这些区域映射与查询谓词进行比较，如果谓词不在段的最小值和最大值之间，则处理可以完全避免从磁盘读取这些块。这称为段消除，类似于分区消除。此外，一些查询可以直接从区域地图中回答，例如“从表中选择最小（列）”

我要指出的是，B 树并不是索引行存储的唯一结构，它只是使用 SQL Server 的数据库开发人员可用的唯一结构。