稀疏/密集索引及其工作原理？
我可以通过搜索一个树来理解B*树索引是如何工作的。
但是，我不知道稀疏索引或密集索引是如何工作的。
例如，如果稠密索引需要由一个键映射每个值。当你做搜索的时候它会有什么好处？
增加更多的澄清：
这个备用/密集索引参考这里描述的wiki：索引上的索引
对于我的理解，索引工作的要点是，您可以搜索B*树作为O(logN)，而不是搜索每个块为O(N)
但是，从稀疏索引或稠密索引的描述。我看不出搜索有什么好处，你是通过钥匙搜索的？但是，键的数量与值相同，对吗？(对于稠密索引，它是严格相等的)
我猜想的是，密集索引和稀疏索引仅仅是B*Tree中使用的索引。但是，我不确定我是否正确地理解了它。因为，我在网上找不到任何东西来证实我的想法。
回答 1
Stack Overflow用户
发布于 2017-06-09 23:18:57
块级稀疏索引
块级稀疏索引只对索引也是聚类的查询有帮助(即索引的排序顺序表示磁盘上数据的局部性)。块级稀疏索引有较少的值，但在开始顺序扫描之前仍然可以找到近似位置。这种情况下的稀疏性实际上是“索引聚集索引中的每个_n_th值”。
从搜索的角度来看，块级稀疏索引查询将：
- 查找小于或等于索引搜索条件的最大键(普通B树大O时间复杂度，即用于搜索的
O(log N)) - 使用该键作为顺序扫描聚集索引的起点(
O(N)用于搜索)
稀疏块级索引的优势主要在于大小，而不是速度:当密集索引(包括所有值)不存在时，较小的稀疏索引可能适合内存。聚集索引上基于范围的查询将返回顺序结果，因此，只要索引不太稀疏以有效支持普通查询，稀疏索引就可能有一些优点。
包含重复键的记录的聚集索引实际上是稀疏索引的一个示例:不需要用相同的值索引每个单独记录的偏移量，因为聚集索引的逻辑顺序与数据的物理顺序匹配。
有关已使用的示例，请参见：稠密稀疏指数 (sfu.ca)。
带有MongoDB选项的sparse索引
不过，我仍然不知道稀疏索引在MongoDB中是如何工作的。例如，您有N个值，字段x不为空。那你的遗嘱就有N把钥匙。那么这把钥匙对你的搜索有什么帮助呢？
带有索引字段的MongoDB索引仅包含具有索引字段的文档的条目。MongoDB具有灵活的模式，因此不需要为集合中的所有文档提供(或相同类型)字段。注意:可选的文档验证是MongoDB 3.2+的一个特性。
默认情况下，集合中的所有文档都将包含在索引中，但是那些没有索引字段的文档将存储null值。如果MongoDB集合中的所有文档都有索引字段的值，则默认索引与带有sparse选项的文档之间没有区别。
这实际上是部分指数的特例:稀疏性是指将索引值的范围限制为只包含非空项。索引方法在其他方面与非稀疏索引相同。
MongoDB文档给出了一个注释：
不要混淆MongoDB中的稀疏索引和其他数据库中的块级索引。将它们视为具有特定筛选器的密集索引。
https://stackoverflow.com/questions/44401351
复制相似问题
腾讯云开发者
