database - DBMS 中的阻塞因子

Question

DBMS 中的阻塞因子是什么，

我看到的那个位表示它是每条记录的 block 的底值(所以 B/R floor)，其中 B 是 block 大小，R 是记录。我只是想知道，有人可以告诉我它被使用的主要原因，以及它是否真的被 FLOORED？

对于任何想知道的人，我对 FLOORED 的理解是 1.5 被降低到 1.0。

Answer 1

Yes, it means how many whole records fit into a block.

( block 是底层存储系统(hdd、san fs 等)愿意处理的最小数据单位。对于硬盘驱动器，它的大小通常为 512 字节。)

它是地板的，因为如果 100 条半记录可以容纳，那么每个 block 只能存储 100 条记录。

在许多与 dbms 相关的计算中，分块因子被大量使用。

例如:

问题

我们有 10 000 000 条记录。每条记录的长度为 80 个字节。每条记录都包含一个唯一的 key (比方说社会安全号码)。我们希望通过社会安全号码快速查找某人。

但是什么是快呢？

我们需要一些东西来衡量性能。花费最多时间的事情是从硬盘请求一个 block 。你知道，它是一种机械装置。它必须重新定位它的头，然后 blabla，所以与 CPU 的速度相比，它确实是一个缓慢的操作，或与操作内存 (RAM) 访问的速度相比。好的，假设我们通过访问磁盘的次数来衡量操作的性能。我们希望最小化磁盘访问次数。好的，现在我们知道如何判断某件事是慢了还是快了。

许多磁盘访问 -> 坏

磁盘访问很少 -> 好

计算我们的数据需要多少 block

假设在我们想象的硬件上，每个 block 是 5000 字节。我们要计算我们需要多少 block 。首先，我们需要知道有多少条记录适合一个 block :

block 因子 = floored(( block 大小)/(记录大小)) = floored(5000/80) = floored(62.5) = 62 条记录/ block

我们有 10000000 条记录，所以我们需要 ceiled(10000000/62)=ceiled(161290.32)=161291 block 来存储所有这些数据。

哇，这么多数据。如何快速查找某人？

如果要读取所有 block 以通过键(社会安全号码)找到一条记录，那么这将需要 161291 次磁盘访问。不好。

我们可以做得更好。让我们构建一个索引文件。我们将构建一个 sparse index .

A sparse index in databases is a file with pairs of keys and pointers for every block in the data file. Every key in this file is associated with a particular pointer to the block in the sorted data file. In clustered indices with duplicate keys, the sparse index points to the lowest search key in each block.

好的，所以我们将在每个 block 的索引文件中有一个指针和一个键。假设在我们想象的硬件上，一个指针有 4 个字节长，而在我们想象的世界中，一个社会安全号码( key )占用 6 个字节。

因此我们将为索引中的每个 block 存储一个 10 字节长的键指针对。这些对中有多少对适合一个 block ？

Blocking factor of the index file = floored(5000/10) = 500

... 所以这意味着 500 个关键指针对适合一个 block 。而我们需要存储其中的 161291 个，因此索引文件将占用 ceiled(161291/500)=323 block

索引文件是按键排序的，所以我们可以在其中进行二进制搜索以找到指向包含记录的 block 的指针。在索引文件中进行二进制搜索最多花费 ceiled(log2(323))=9 磁盘访问。我们还需要 +1 磁盘访问权限来实际读取索引记录指向的数据 block 。

哇，我们的查找在 10 次磁盘访问中工作。太棒了。我们甚至可以做得更好。 :)

好的，所以您可以看到在这个计算中使用了大量的分块因子。