与写入数据库索引相比的读取次数

Question

众所周知，数据库索引只有在有大表时才有意义，而且读取量大于写入量，因为索引的创建会导致额外的写入开销，因为数据库中的每次修改都会导致索引的修改。

如果我们假设数据库的索引结构是( a)一个B+树( b)一个哈希表，那么与实现数据库索引开始有意义的写入数相比，读取次数的经验规则是什么？

有关数据库索引工作方式的信息，请参阅How does database indexing work?。

Answer 1

这里涉及到许多因素。例如，缓存中是否有索引数据？缓存中有数据块吗？查询检索了多少行？锄头，表格中的许多行，等等，我已经被问了很多次这个问题(或它的一个变体)。与其给出数字，我更愿意提供一些信息，这样提问的人才能做出明智的决定。这里是一个“信封背面”的计算例子，并有一些陈述的假设。

1. 假设这张表有100行
2. 假设一行平均为200个字节( )
   • 比表消耗大约19 any (忽略任何压缩)

​

1. 让我们假设索引是完全缓存的，并且花费的时间为零。
2. 假设数据必须从磁盘读取，每次读取5ms。
3. 让我们假设您的IO子系统可以以10 GB/s的速度传送数据。
4. 假设您需要从表中读取50,000行。我们还假设行是分布在一起的，因此两个所需的行位于同一个块中。 好的，现在我们可以做一些数学了。 场景1.使用索引

- Index reads are zero time
- Data block reads: 25,000 blocks @5ms each is 125s

场景2.扫描表

- 19GB scanned at 10GB/s is 2s

因此，在这种情况下，扫描数据要比使用索引快得多。

Answer 2

费用公式

什么也没有：

• 插入: O(1)
• 搜索O(n)
• 成本搜索=n db查找操作
• 成本插入= db插入

( a) b阶B+树

• 插入:O(对数n)
• 搜索:O(日志n)
• 成本搜索= log_b n查找操作+ db查找
• 成本插入= log_b n查找操作+ db insert
• 随着订单的增加，查找操作的数量减少，但每次查找操作的成本增加。

b) Hashtable

• 插入: O(1)
• 搜寻: O(1)
• 成本搜索=哈希计算+碰撞发生时的额外桶+ db查找
• 成本插入=哈希计算+碰撞发生时的额外桶+ db插入

成本按n= 1000计算

什么也没有：

• 成本搜索= 1000 db查找操作
• 成本插入=1 db插入

( a1) 2阶B+树

• 成本搜索=10个查找操作+1 db查找
• 成本插入=10个查找操作+1 db插入

a2) 10阶B+树

• 成本搜索=3次查找操作+1 db查找
• 成本插入=3个查找操作+1 db插入

b) Hashtable

• 成本搜索=哈希计算+碰撞发生时的额外桶+ db查找
• 成本插入=哈希计算+碰撞发生时的额外桶+ db插入

成本n= 1000000

什么也没有：

• 成本搜索= 1000000 db查找操作
• 成本插入=1 db插入

( a1) 2阶B+树

• 成本搜索=20个查找操作+1 db查找
• 成本插入=20个查找操作+1 db插入

a2) 10阶B+树

• 成本搜索=6个查找操作+1 db查找
• 成本插入=6个查找操作+1 db插入

b) Hashtable

• 成本搜索=哈希计算+碰撞发生时的额外桶+ db查找
• 成本插入=哈希计算+碰撞发生时的额外桶+ db插入

也有相当大的成本收益，可以通过击中硬件缓存的后续命中。准确的收益取决于安装数据库的硬件。

成本并不都是很容易比较的。哈希计算通常比查找更昂贵，但当n变大时，则保持不变。B树查找和顺序DB查找可能会到达硬件缓存(因为加载了整个块)。

表越大，索引就越重要(参见n=1000对n=1000000的成本)。因此，写入和读取的数量将随表的大小而变化。

您还应该考虑到您的特定查询。例如，哈希表没有排序，而B树是排序的。因此，如果查询需要获取最小值和最大值之间的所有值，B树的性能将优于哈希表(良好的哈希是均匀分布的)。

通常，您必须度量查询和实际使用的插入的性能。您可以在没有索引的情况下开始，然后在需要时添加索引。以后可以添加索引，而不必使用DB更改程序的查询(不过，查询的响应时间会改变，如果使用索引，读取将变得更快，写入将变得更慢)。

如果在特定情况下，您有一个包含大量插入和一个读取周期的load操作，则可以暂时关闭索引并在加载后重新计算它。

参考文献：

B树与哈希表：

https://cs.stackexchange.com/questions/270/hash-tables-versus-binary-trees

缓存

http://www.moreprocess.com/devices/computer-memory-hierarchy-internal-register-cache-ram-hard-disk-magnetic-tape

Answer 3

使用数据库的目的通常是减少在数据中查找某物的时间，因此它是关于“阅读”的。我非常肯定，90%的人使用数据库来“阅读”，如果不是100%的话。

让我们想想几个例子：

• 只写，不读：有什么意义？只是作为后援？那么，备份将在恢复时用于读取。
• 很多人写，很少有人读：我想不出这种情况，但是当你有这种情况时，你更看重哪一种呢？迅速呈现数据？或者你保存数据的速度？如果您评估数据保存的速度，那么您可以删除索引，并有一个夜间运行来显示数据(考虑到数据保存的速度，它足够大到需要一夜运行来总结数据)，因此您可以进行近乎实时的写入，H+1或更晚的数据读取，这就产生了疑问:有这样的配置有什么意义？
• 很少写，很多人读：这是最常见的情况
• 不写，只读：100%你不能产生这种情况，没有写那么读什么？

对不起我的英语，希望它能帮上忙