为什么使用有序索引，但是程序员使用哈希表？

以下是翻译:

我可以肯定地说，哈希表比有序数据结构普遍得多. Go中的map，Python中的dict，Java中的HashMap等都是哈希表，而树结构仅保持顺序. 仅在数据结构时使用. 有一次，当谈到Google的优化的C ++哈希表时，有人指出Google服务器中的哈希表使用了1％的CPU和4％的内存. 但是，默认情况下，始终使用有序索引，通常是B树. 为什么程序和之间的“默认”选择不同？毕竟，两者都是出于同一目标: 访问数据. 一年前，我在Twitter上发布了有关此问题的推文，并获得了许多有趣的答案. 让我总结一下我得到的答案.

常见的答案是，将数据存储在内存中时，哈希表的效率非常高，并且B树的设计旨在以块的形式访问较慢的存储. 但是，这不是决定性的属性. 我们还有用于访问磁盘的哈希表，例如MySQL的哈希索引. 内存中还使用了许多树，例如Java的TreeMap，C ++映射；甚至B树也有用于内存的版本.

我认为最重要的答案是B树更适合“通用”，它们可以以较低的总成本访问持久数据. 换句话说，即使在访问大多数工作负载为单个值的数据时，B树也较慢，但考虑到罕见的操作和多个索引的成本，B树的性能仍然更加突出. 在本文中，我将简要解释哈希表和B树之间的区别，然后讨论持久性数据和内存数据的需求之间的区别. 最后，尽管我认为“内存应使用有序数据结构而应使用哈希表”的默认做法可能是正确的，但我仍然会提出自己的一些看法.

哈希表和树

首先，让我们回顾一下这些数据结构之间的根本差异. 访问单个值时，哈希表的访问时间为常数O（1），树的访问时间为对数O（log n）. 对于单值查找，这意味着无论数据存储在内存中还是磁盘上，哈希表都更快. 但是，尽管增加了树的成本，树中的值还是有序的. 因此，我们可以有效地访问范围值，这意味着它们可以有效地支持多种操作. 例如，我们可以找到以某个前缀开头的所有值或``前k个''值，如果我们将其替换为哈希表，则需要扫描整个表. 关于中B树的使用，我强烈建议您阅读“现代B树技术”（）. 作者Goetz Graefe在书中提出了一个微妙，易于理解和全面的.

另一个差异是散列表仅提供平均的恒定时间访问. 有意或无意的哈希冲突可能会导致不良行为，但更大的问题是重新哈希. 有时，随着表的增加，原本需要O（1）的插入操作可能需要缓慢的O（n）扫描才能将数据插入到较大的表中. 我们可以通过使用多级哈希表来减少这种影响，但是它仍然会导致一些不可预测的情况. 相反，最坏的树可以维持O（log n）.

持久性数据和内存数据

通常，用于存储需要永久存在的持久性数据. 程序通常仅需要临时存储数据，并且仅在需要重新启动时才需要持久存储. 这意味着最终将经常存储大量数据，无论是记录数还是字节总数非常大. 出于以下三个原因，我认为使用有序数据结构更好:

1. 到了n个小时，数据结构并不是特别重要

我认为程序中的大多数哈希表非常小，只有数千个元素或更少. 在这种规模下，O（1），O（log n）和O（n）之间的差异无关紧要. 因此，在程序中，哈希表对于常见的单值查找更快. 对于罕见的全表扫描，哈希表会稍微慢一些. 但是，随着数据集的增长，找到相关的值需要O（n），这使人们感到太慢了.

具体来说，假设在一个应用程序中，将99％的访问限制为单个记录，只有1％的访问涉及10个连续记录，并且需要从某个值开始. 此时，如果我们使用哈希表，则访问单个记录的成本为1，而访问特定范围的成本为n（扫描整个表），因此总成本为0.99×1 + 0.01×n . 如果我们使用树，则访问单个记录的成本为log（n），而访问范围的成本为log（n）+9，因此总成本为0.99×log（n）+ 0.01×（log （n）+ 9）. 如下图所示:

当然，我在这里弥补了“开销”，但是我们可以看到趋势: 如果n小，那么哈希表是一个更好的选择；但是，如果n较大，那么即使扫描整个表，该操作也非常少见，并且也将对总成本产生很大影响. 这就是我们经常说的O（n）与O（log n）之间的比较，这意味着在处理大型数据集时，有序数据结构的性能更加“平衡”具有巨大的优势.

2. 存储不是免费的

如果元素的数量很少，则相对便宜的方法是存储数据的多个副本并创建不同的索引. 程序和都使用此技术. 但是，添加索引需要O（n）的存储空间和O（n）的构建时间. 对于非常大的，添加二级索引可能需要数小时甚至数天. 因此，数据大小越大，在不同类型的查询中重用索引的优势就越大. 这对于有序索引是一个优势，因为我们可以通过多种方式使用有序属性. 例如，一种常见的技术是创建具有多个列的索引，例如（位置，商店名称）. 然后基于hash表的索引结构设计与实现，我们可以使用该索引来访问特定的（位置，商店名称），还可以记录单个（位置），甚至是位置键的前缀. 如果它是哈希表基于hash表的索引结构设计与实现，则每个查询都需要一个单独的索引.

3. 持久数据结构更复杂

将数据存储在磁盘上，以便在机器崩溃时不会损坏或丢失数据. 您需要按顺序仔细地写数据，在写数据之前记录日志，并且还可能需要详细的并发控制. 与存储器数据结构相比，这些操作需要更多代码. 因此，许多仅支持一种类型的持久索引. 如果只选择一个索引，那么即使效率稍低，最好也选择一个可以广泛用于各种负载的索引.

这种额外的复杂性意味着，除了必需的数据结构访问之外，您还需要完成更多的工作，这将对常量因素产生很大的影响. 例如，您需要通过网络发送请求，进行解析，从磁盘复制一些数据，进行解析，获取锁等. 这些将减少O（1）和O（log N）之间的差异.

总结和教训

我认为默认情况下，正确的选择是在程序中使用哈希表，在中使用有序数据结构. 但是，在许多情况下，我们可能使用错误的选择. 我怀疑许多程序无法有效利用有序数据结构，因为相比之下，顺序迭代的难度要小得多. 例如，如果我有两个按时间排序的集合，并且我想按时间顺序输出合并的集合，则可以同时迭代这两个集合并从适当的迭代中选择数据. 但是，我也可以将所有事件放在列表中，对它们进行排序并输出. 我知道我会首先想到哪个. 这种复杂性的折衷让我感到奇怪: 使用集合时是否有一种嵌入查询优化的方法...

原文:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-189500-1.html