聚集索引与非聚集索引，类似于数组与链表？

Question

我刚开始担任 DBA，最近对索引以及它们如何加速查询感兴趣。我在这里阅读了有关索引的信息：https : //msdn.microsoft.com/en-us/library/ms190457.aspx并试图了解 SQL Server 中聚集索引和非聚集索引之间的区别。

从我读到的内容来看，这听起来像是聚集索引对数据进行排序，因此索引总是“知道”下一个值所在的位置，就在它的旁边。这让我想起了一个具有连续内存的数组。类似地，非聚集索引听起来像一个链表，因为索引的一部分保存了值，还有一部分指向下一个索引。这是一个恰当的比较吗？

Answer 1

嗯...聚集索引的叶级是SQL Server 中的表。这类似于电话簿（从@BrentO借用），因为书中的所有条目都按索引的顺序存储 - 即索引按字母顺序逻辑排序（如果没有碎片，则在物理上排序）。这有点类似于物理上连续的内存中数组，尽管 SQL Server 不能保证数据连续存储在磁盘上或物理顺序。任一索引类型的叶级别的每个页面都是双向链表的一部分，并具有按键顺序指向前一页和下一页的指针，有序索引扫描使用这些指针按键顺序遍历索引。

非聚集索引类似于书后的索引，因为索引本身是经过排序的，因此很容易在索引中查找项目。您可能有两个非聚集索引，一个按电话号码列出所有电话簿条目，另一个按地址列出所有电话簿条目。聚集索引（实际的电话簿）按电话号码所有者的姓名进行物理布局。这是有道理的，因为您通常通过“所有者姓名”“查找”电话号码。这有点类似于内存中指向实际数据位置的连续指针数组。该数组仅包含索引详细信息。

如果您只知道一个人的电话号码，并且需要知道他们的姓名，那么通过逐个姓名地翻阅整本书来查找姓名确实需要很长时间才能找到该号码，而您可以简单地查看电话号码索引以找到所有者的姓名。这就是非聚集索引的工作原理。

Answer 2

区别不像数组与链表（两者都是数据结构 - 但不是正确的。）。两种类型的索引都使用 B 树（数据结构）来组织数据。不同之处在于 B 树的组织方式。

对于聚集索引，数据在数据结构中组织，叶子在磁盘上物理组织。这有几个含义： 1) 增加插入的开销。2) 加快整个搜索速度，因为磁盘读取器磁头不必走遍整个磁盘来查找内容，并且 3) 每个表只能创建 1 个聚集索引。

对于非聚集索引，B-Tree 索引就像聚集索引一样，只是叶节点仅包含指向磁盘上物理位置的指针。这意味着每桌可以有超过 1 个。虽然这不如集群那么快，因为所有数据都以已知的、有组织的方式存在，但它至少是系统可以查找数据所在位置的位置，而不必扫描整个磁盘。

来源：https ://msdn.microsoft.com/en-us/library/ms190457.aspx