0

我正在编写一个数据库，我希望为特定类型的每个项目分配一个唯一 ID（用于内部数据管理）。但是，预计数据库将运行很长时间（理论上无限），并且条目的周转率很高（例如定期删除和添加条目）。

如果我们将我们的唯一 ID 建模为unsigned int，并假设数据库中的条目总是少于2^32 - 1（我们不能0用作唯一 ID），我们可以执行以下操作：

void GenerateUniqueID( Object* pObj )
{
    static unsigned int iCurrUID = 1;
    pObj->SetUniqueID( iCurrUID++ );
}

但是，在开始删除条目并在其位置添加其他条目之前，这很好，可能仍然少于2^32-1条目，但我们可能会溢出iCurrUID并最终分配已经被使用的“唯一”ID。

我的一个想法是使用 astd::bitset<std::numeric_limits<unsigned int>::max-1>然后遍历它来找到第一个免费的唯一 ID，但这会消耗大量内存并且需要线性复杂度才能找到一个免费的唯一 ID，所以我正在寻找一种更好的方法，如果一个存在吗？

提前致谢！

我知道将数据类型更改为 64 位整数而不是 32 位整数可以解决我的问题；但是，因为我在 Win32 环境中工作，并且使用列表（DWORD_PTR32 位），所以我正在寻找替代解决方案。此外，数据是通过网络发送的，我试图通过使用较小的唯一 ID 来减少带宽消耗。

4

2 回答 2

6

使用 uint64_t（64 位），即使您每秒插入接近 100k 个条目，它也会花费您超过 100 年的时间。超过 100 年，您应该插入大约 315,360,000,000,000 条记录（不考虑闰年和闰秒等）。这个数字将适合 49 位。

您预计该应用程序将运行多长时间？超过100年？

这是数据库管理员在拥有接近 32 位限制的自动增量字段时所做的常见事情。他们将值更改为数据库系统的本机 64 位类型（或 128 位）。

于 2013-09-10T11:32:55.703 回答
1

真正的问题是，在保证删除第一个条目之前，您可以拥有多少条目。以及创建新条目的频率。保证Anunsigned long long的最大值至少为 2^64，大约为 1.8x10^19。即使每微秒创造一个，这也将持续几千个世纪。实际上，您将无法快速创建条目（因为磁盘速度不允许），并且您的程序不会运行数百个世纪（因为硬件不会持续那么久） . 如果唯一 id 用于基于磁盘的某些东西，那么您可以安全地使用unsigned long long该 id。

否则，当然，生成您认为可能需要的尽可能多的位。如果你真的很偏执，那么使用 256 位无符号整数甚至更长的时间都是微不足道的。在某个时候，即使宇宙中的每个原子每皮秒创建一个新条目，直到宇宙尽头，你也会没事的。（但实际上……unsigned long long应该足够了。）

于 2013-09-10T11:41:10.840 回答