检索16k键值对的最快方法是什么？

好的，这是我的情况：

• 我有一个函数 – 比方说U64 calc (U64 x) – 它采用64位整数参数，执行一些CPU密集型操作，并返回64位值
• 现在，鉴于我事先知道了该函数的所有可能输入（ x s）（虽然有大约16000），我认为预先计算它们然后根据需要获取它们（从类似数组的结构）可能更好）。
• 理想的情况是将它们全部存储在某个数组U64 CALC[]并通过索引检索它们（再次为x ）
• 这就是问题所在：我可能知道我的calc函数的可能输入是什么，但它们绝对不是连续的 （例如，不是从1到16000，而是可能低至0且高达数万亿的值 – 总是具有64位范围）

例如

  X CALC[X] ----------------------- 123123 123123123 12312 12312312 897523 986123 etc. 

这是我的问题：

• 你会如何存储它们？
• 您更喜欢哪种解决方法？
• 现在，鉴于这些值（来自CALC ） 每秒必须访问数千到数百万次 ，这将是性能最佳的解决方案吗？

---

注意 ：我没有提到我曾经想过或试过的任何事情，以免把答案变成A和B类型的辩论，而且大部分都没有影响到任何人……

Answer 1

我会使用某种哈希函数来创建一个u64对的索引，其中一个是创建密钥的值，另一个是替换值。 从技术上讲，索引可能是三个字节长（假设1600万 – “16000千” – 对），如果你需要节省空间但我会使用u32s。 如果存储的值与（哈希冲突）上计算的值不匹配，则输入溢出处理程序。

• 您需要确定自定义哈希算法以适合您的数据
• 由于您知道数据的大小，因此您不需要允许数据增长的算法。
• 我会谨慎使用一些标准算法，因为它们很少适合特定数据
• 除非你确定代码是WYSIWYG（不产生很多不可见的调用），否则我会谨慎使用C ++方法
• 您的索引应该比对的数量大25％

运行所有可能的输入并确定碰撞次数的最小值，最大值，平均值和标准差，并使用这些来确定可接受的性能级别。 然后配置文件以实现最佳代码。

所需的内存空间（使用u32索引）为每对（4 * 1.25）+ 8 + 8 = 21字节或336 MeB，在典型PC上没问题。

________ EDIT________

我受到了“RocketRoy”的挑战，把我的钱放在嘴边。 开始：

问题与（固定大小）哈希索引中的冲突处理有关。 设置阶段：

• 我有一个n个条目的列表，其中条目中的字段包含计算散列的值v
• 我有一个n * 1.25（大约）indeces的向量，使得indeces x的数量是素数
• 计算素数y，其是x的分数
• 向量初始化为-1表示未占用

非常标准的东西，我想你会同意的。

处理列表中的条目，并计算和模数化散列值，并将其用作向量的索引，并将条目的索引放在那里。

最终我遇到了索引指向的向量条目被占用（不包含-1）的情况 – vo vo，一个碰撞。

那我该怎么办？ 我将原始h保持为ho，将y添加到h并取模x并获得向量中的新索引。 如果条目未被占用我使用它，否则我继续添加y modulo x直到我达到ho。 理论上，这将发生，因为x和y都是素数。 在实践中，x大于n，所以它不会。

因此RocketRoy声称的“重新哈希”非常昂贵并非如此。

这种方法的棘手部分 – 与所有散列方法一样 – 是：

• 确定x的合适值（最终使用的较大x变得不那么棘手）
• 确定h = a（v）％x的算法a，使得h的索引合理地均匀（“随机”）到索引向量中，尽可能少的碰撞
• 确定y的合适值，使得碰撞合理地均匀地（“随机地”）索引到索引向量中

________ EDIT________

对不起，我花了这么长时间来制作这个代码……其他的东西都有更高的优先级。

无论如何，这里的代码certificate了哈希比二叉树具有更好的快速查找前景。 它运行一系列散列索引大小和算法，以帮助找到特定数据的最合适的组合。 对于每个算法，代码将打印第一个索引大小，使得查找不会超过十四次搜索（二进制搜索的最坏情况），并且平均查找需要少于1.5次搜索。

如果您没有注意到，我会喜欢这些类型的应用中的素数。

有许多方法可以通过强制溢出处理来创建散列算法。 我选择了简单，假设它会转化为速度……而且确实如此。 在我的i5 M 480 @ 2.67 GHz笔记本电脑上，平均查找需要55到60个时钟周期（每秒查找大约4500万次）。 我使用常量的indeces和ditto rehash值实现了一个特殊的get操作，循环次数降至40（每秒6500万次查找）。 如果你看一下调用getOpSpec的行，索引i与0x444进行xor’ed来运行缓存以获得更多“真实世界”的结果。

我必须再次指出，该计划建议适合特定数据的组合。 其他数据可能需要不同的组合。

源代码包含用于生成16000个无符号长长对的代码以及用于测试不同常量（索引大小和重新散列值）的代码：

 #include  #define i8 signed char #define i16 short #define i32 long #define i64 long long #define id i64 #define u8 char #define u16 unsigned short #define u32 unsigned long #define u64 unsigned long long #define ud u64 #include  #include  u64 prime_find_next (const u64 value); u64 prime_find_previous (const u64 value); static inline volatile unsigned long long rdtsc_to_rax (void) { unsigned long long lower,upper; asm volatile( "rdtsc\n" : "=a"(lower), "=d"(upper)); return lower|(upper<<32); } static u16 index[65536]; static u64 nindeces,rehshFactor; static struct PAIRS {u64 oval,rval;} pairs[16000] = { #include "pairs.h" }; struct HASH_STATS { u64 ninvocs,nrhshs,nworst; } getOpStats,putOpStats; i8 putOp (u16 index[], const struct PAIRS data[], const u64 oval, const u64 ci) { u64 nworst=1,ho,h,i; i8 success=1; ++putOpStats.ninvocs; ho=oval%nindeces; h=ho; do { i=index[h]; if (i==0xffff) /* unused position */ { index[h]=(u16)ci; goto added; } if (oval==data[i].oval) goto duplicate; ++putOpStats.nrhshs; ++nworst; h+=rehshFactor; if (h>=nindeces) h-=nindeces; } while (h!=ho); exhausted: /* should not happen */ duplicate: success=0; added: if (nworst>putOpStats.nworst) putOpStats.nworst=nworst; return success; } i8 getOp (u16 index[], const struct PAIRS data[], const u64 oval, u64 *rval) { u64 ho,h,i; i8 success=1; ho=oval%nindeces; h=ho; do { i=index[h]; if (i==0xffffu) goto not_found; /* unused position */ if (oval==data[i].oval) { *rval=data[i].rval; /* fetch the replacement value */ goto found; } h+=rehshFactor; if (h>=nindeces) h-=nindeces; } while (h!=ho); exhausted: not_found: /* should not happen */ success=0; found: return success; } volatile i8 stop = 0; int main (int argc, char *argv[]) { u64 i,rval,mulup,divdown,start; double ave; SetThreadAffinityMask (GetCurrentThread(), 0x00000004ull); divdown=5; //5 while (divdown<=100) { mulup=3; // 3 while (mulup 

无法包含生成的对文件（答案显然限制为30000个字符）。 但是发送邮件到我的收件箱，我会邮寄它。

这些是结果：

 3;5;35569;21323;1.390;14;73 3;7;33577;14389;1.435;14;60 5;7;32069;22901;1.474;14;61 3;11;35107;9551;1.412;14;59 5;11;33967;15427;1.446;14;61 7;11;34583;22003;1.422;14;59 3;13;34253;7901;1.439;14;61 5;13;34039;13063;1.443;14;60 7;13;32801;17659;1.456;14;60 11;13;33791;28591;1.436;14;59 3;17;34337;6053;1.413;14;59 5;17;32341;9511;1.470;14;61 7;17;32507;13381;1.474;14;62 11;17;33301;21529;1.454;14;60 13;17;34981;26737;1.403;13;59 3;19;33791;5333;1.437;14;60 5;19;35149;9241;1.403;14;59 7;19;33377;12289;1.439;14;97 11;19;34337;19867;1.417;14;59 13;19;34403;23537;1.430;14;61 17;19;33923;30347;1.467;14;61 3;23;33857;4409;1.425;14;60 5;23;34729;7547;1.429;14;60 7;23;32801;9973;1.456;14;61 11;23;33911;16127;1.445;14;60 13;23;33637;19009;1.435;13;60 17;23;34439;25453;1.426;13;60 19;23;33329;27529;1.468;14;62 3;29;32939;3391;1.474;14;62 5;29;34543;5953;1.437;13;60 7;29;34259;8263;1.414;13;59 11;29;34367;13033;1.409;14;60 13;29;33049;14813;1.444;14;60 17;29;34511;20219;1.422;14;60 19;29;33893;22193;1.445;13;61 23;29;34693;27509;1.412;13;92 3;31;34019;3271;1.441;14;60 5;31;33923;5449;1.460;14;61 7;31;33049;7459;1.442;14;60 11;31;35897;12721;1.389;14;59 13;31;35393;14831;1.397;14;59 17;31;33773;18517;1.425;14;60 19;31;33997;20809;1.442;14;60 23;31;34841;25847;1.417;14;59 29;31;33857;31667;1.426;14;60 3;37;32569;2633;1.476;14;61 5;37;34729;4691;1.419;14;59 7;37;34141;6451;1.439;14;60 11;37;34549;10267;1.410;13;60 13;37;35117;12329;1.423;14;60 17;37;34631;15907;1.429;14;63 19;37;34253;17581;1.435;14;60 23;37;32909;20443;1.453;14;61 29;37;33403;26177;1.445;14;60 31;37;34361;28771;1.413;14;59 3;41;34297;2503;1.424;14;60 5;41;33587;4093;1.430;14;60 7;41;34583;5903;1.404;13;59 11;41;32687;8761;1.440;14;60 13;41;34457;10909;1.439;14;60 17;41;34337;14221;1.425;14;59 19;41;32843;15217;1.476;14;62 23;41;35339;19819;1.423;14;59 29;41;34273;24239;1.436;14;60 31;41;34703;26237;1.414;14;60 37;41;33343;30089;1.456;14;61 3;43;34807;2423;1.417;14;59 5;43;35527;4129;1.413;14;60 7;43;33287;5417;1.467;14;61 11;43;33863;8647;1.436;14;60 13;43;34499;10427;1.418;14;78 17;43;34549;13649;1.431;14;60 19;43;33749;14897;1.429;13;60 23;43;34361;18371;1.409;14;59 29;43;33149;22349;1.452;14;61 31;43;34457;24821;1.428;14;60 37;43;32377;27851;1.482;14;81 41;43;33623;32057;1.424;13;59 3;47;33757;2153;1.459;14;61 5;47;33353;3547;1.445;14;61 7;47;34687;5153;1.414;13;59 11;47;34519;8069;1.417;14;60 13;47;34549;9551;1.412;13;59 17;47;33613;12149;1.461;14;61 19;47;33863;13687;1.443;14;60 23;47;35393;17317;1.402;14;59 29;47;34747;21433;1.432;13;60 31;47;34871;22993;1.409;14;59 37;47;34729;27337;1.425;14;59 41;47;33773;29453;1.438;14;60 43;47;31253;28591;1.487;14;62 3;53;33623;1901;1.430;14;59 5;53;34469;3229;1.430;13;60 7;53;34883;4603;1.408;14;59 11;53;34511;7159;1.412;13;59 13;53;32587;7963;1.453;14;60 17;53;34297;10993;1.432;13;80 19;53;33599;12043;1.443;14;64 23;53;34337;14897;1.415;14;59 29;53;34877;19081;1.424;14;61 31;53;34913;20411;1.406;13;59 37;53;34429;24029;1.417;13;60 41;53;34499;26683;1.418;14;59 43;53;32261;26171;1.488;14;62 47;53;34253;30367;1.437;14;79 3;59;33503;1699;1.432;14;61 5;59;34781;2939;1.424;14;60 7;59;35531;4211;1.403;14;59 11;59;34487;6427;1.420;14;59 13;59;33563;7393;1.453;14;61 17;59;34019;9791;1.440;14;60 19;59;33967;10937;1.447;14;60 23;59;33637;13109;1.438;14;60 29;59;34487;16943;1.424;14;59 31;59;32687;17167;1.480;14;61 37;59;35353;22159;1.404;14;59 41;59;34499;23971;1.431;14;60 43;59;34039;24799;1.445;14;60 47;59;32027;25471;1.499;14;62 53;59;34019;30557;1.449;14;61 3;61;35059;1723;1.418;14;60 5;61;34351;2803;1.416;13;60 7;61;35099;4021;1.412;14;59 11;61;34019;6133;1.442;14;60 13;61;35023;7459;1.406;14;88 17;61;35201;9803;1.414;14;61 19;61;34679;10799;1.425;14;101 23;61;34039;12829;1.441;13;60 29;61;33871;16097;1.446;14;60 31;61;34147;17351;1.427;14;61 37;61;34583;20963;1.412;14;59 41;61;32999;22171;1.452;14;62 43;61;33857;23857;1.431;14;98 47;61;34897;26881;1.431;14;60 53;61;33647;29231;1.434;14;60 59;61;32999;31907;1.454;14;60 3;67;32999;1471;1.455;14;61 5;67;35171;2621;1.403;14;59 7;67;33851;3533;1.463;14;61 11;67;34607;5669;1.437;14;60 13;67;35081;6803;1.416;14;61 17;67;33941;8609;1.417;14;60 19;67;34673;9829;1.427;14;60 23;67;35099;12043;1.415;14;60 29;67;33679;14563;1.452;14;61 31;67;34283;15859;1.437;14;60 37;67;32917;18169;1.460;13;61 41;67;33461;20443;1.441;14;61 43;67;34313;22013;1.426;14;60 47;67;33347;23371;1.452;14;61 53;67;33773;26713;1.434;14;60 59;67;35911;31607;1.395;14;58 61;67;34157;31091;1.431;14;63 3;71;34483;1453;1.423;14;59 5;71;34537;2423;1.428;14;59 7;71;33637;3313;1.428;13;60 11;71;32507;5023;1.465;14;79 13;71;35753;6529;1.403;14;59 17;71;33347;7963;1.444;14;61 19;71;35141;9397;1.410;14;59 23;71;32621;10559;1.475;14;61 29;71;33637;13729;1.429;14;60 31;71;33599;14657;1.443;14;60 37;71;34361;17903;1.396;14;59 41;71;33757;19489;1.435;14;61 43;71;34583;20939;1.413;14;59 47;71;34589;22877;1.441;14;60 53;71;35353;26387;1.418;14;59 59;71;35323;29347;1.406;14;59 61;71;35597;30577;1.401;14;59 67;71;34537;32587;1.425;14;59 3;73;34613;1409;1.418;14;59 5;73;32969;2251;1.453;14;62 7;73;33049;3167;1.448;14;61 11;73;33863;5101;1.435;14;60 13;73;34439;6131;1.456;14;60 17;73;33629;7829;1.455;14;61 19;73;34739;9029;1.421;14;60 23;73;33071;10399;1.469;14;61 29;73;33359;13249;1.460;14;61 31;73;33767;14327;1.422;14;59 37;73;32939;16693;1.490;14;62 41;73;33739;18947;1.438;14;60 43;73;33937;19979;1.432;14;61 47;73;33767;21739;1.422;14;59 53;73;33359;24203;1.435;14;60 59;73;34361;27767;1.401;13;59 61;73;33827;28229;1.443;14;60 67;73;34421;31583;1.423;14;71 71;73;33053;32143;1.447;14;60 3;79;35027;1327;1.410;14;60 5;79;34283;2161;1.432;14;60 7;79;34439;3049;1.432;14;60 11;79;34679;4817;1.416;14;59 13;79;34667;5701;1.405;14;59 17;79;33637;7237;1.428;14;60 19;79;34469;8287;1.417;14;60 23;79;34439;10009;1.433;14;60 29;79;33427;12269;1.448;13;61 31;79;33893;13297;1.445;14;61 37;79;33863;15823;1.439;14;60 41;79;32983;17107;1.450;14;60 43;79;34613;18803;1.431;14;60 47;79;33457;19891;1.457;14;61 53;79;33961;22777;1.435;14;61 59;79;32983;24631;1.465;14;60 61;79;34337;26501;1.428;14;60 67;79;33547;28447;1.458;14;61 71;79;32653;29339;1.473;14;61 73;79;34679;32029;1.429;14;64 3;83;35407;1277;1.405;14;59 5;83;32797;1973;1.451;14;60 7;83;33049;2777;1.443;14;61 11;83;33889;4483;1.431;14;60 13;83;35159;5503;1.409;14;59 17;83;34949;7151;1.412;14;59 19;83;32957;7541;1.467;14;61 23;83;32569;9013;1.470;14;61 29;83;33287;11621;1.474;14;61 31;83;33911;12659;1.448;13;60 37;83;33487;14923;1.456;14;62 41;83;33587;16573;1.438;13;60 43;83;34019;17623;1.435;14;60 47;83;31769;17987;1.483;14;62 53;83;33049;21101;1.451;14;61 59;83;32369;23003;1.465;14;61 61;83;32653;23993;1.469;14;61 67;83;33599;27109;1.437;14;61 71;83;33713;28837;1.452;14;61 73;83;33703;29641;1.454;14;61 79;83;34583;32911;1.417;14;59 3;89;34147;1129;1.415;13;60 5;89;32797;1831;1.461;14;61 7;89;33679;2647;1.443;14;73 11;89;34543;4261;1.427;13;60 13;89;34603;5051;1.419;14;60 17;89;34061;6491;1.444;14;60 19;89;34457;7351;1.422;14;79 23;89;33529;8663;1.450;14;61 29;89;34283;11161;1.431;14;60 31;89;35027;12197;1.411;13;59 37;89;34259;14221;1.403;14;59 41;89;33997;15649;1.434;14;60 43;89;33911;16127;1.445;14;60 47;89;34949;18451;1.419;14;59 53;89;34367;20443;1.434;14;60 59;89;33791;22397;1.430;14;59 61;89;34961;23957;1.404;14;59 67;89;33863;25471;1.433;13;60 71;89;35149;28031;1.414;14;79 73;89;33113;27143;1.447;14;60 79;89;32909;29209;1.458;14;61 83;89;33617;31337;1.400;14;59 3;97;34211;1051;1.448;14;60 5;97;34807;1789;1.430;14;60 7;97;33547;2417;1.446;14;60 11;97;35171;3967;1.407;14;89 13;97;32479;4349;1.474;14;61 17;97;34319;6011;1.444;14;60 19;97;32381;6337;1.491;14;64 23;97;33617;7963;1.421;14;59 29;97;33767;10093;1.423;14;59 31;97;33641;10739;1.447;14;60 37;97;34589;13187;1.425;13;60 41;97;34171;14437;1.451;14;60 43;97;31973;14159;1.484;14;62 47;97;33911;16127;1.445;14;61 53;97;34031;18593;1.448;14;80 59;97;32579;19813;1.457;14;61 61;97;34421;21617;1.417;13;60 67;97;33739;23297;1.448;14;60 71;97;33739;24691;1.435;14;60 73;97;33863;25471;1.433;13;60 79;97;34381;27997;1.419;14;59 83;97;33967;29063;1.446;14;60 89;97;33521;30727;1.441;14;60 

Cols 1和2用于计算rehash值和索引大小之间的粗略关系。 接下来的两个是第一个索引大小/重新连接因子组合，平均少于1.5次搜索，查找最差情况下的14次搜索。 然后平均和最坏的情况。 最后，最后一列是每次查找的平均时钟周期数。 它没有考虑读取时间戳寄存器所需的时间。

最佳常数（＃of indeces = 31253和rehash factor = 28591）的实际存储空间超出了我最初的指示（16000 * 2 * 8 + 1,25 * 16000 * 2 => 296000字节）。 实际尺寸为16000 * 2 * 8 + 31253 * 2 => 318506。

最快的组合是大约11/31的比率，索引大小为35897，rehash值为12721.这将平均为1.389（1个初始散列+ 0.389个重新散列），最大值为14（1 + 13）。

________ EDIT________

我删除了“goto found;” 在main（）中显示所有组合，它表明可以获得更好的性能，当然是以更大的索引大小为代价。 例如，组合57667和33797产生并且平均值为1.192，最大重新组合为6.组合44543和23399产生1.249平均值和10个最大重新组合（它保存（57667-44543）* 2 = 26468字节的索引表与33797分之57667）。

与变量相比，具有硬编码哈希索引大小和重新哈希因子的专用函数将在60-70％的时间内执行。 这可能是由于编译器（gcc 64位）用乘法代替模数而不必从存储器位置取值，因为它们将被编码为立即值。

________ EDIT________

关于缓存的问题，我看到两个问题。

第一个是数据缓存，我认为这是不可能的，因为查找只是在一个更大的进程中的一小步，并且你冒着表数据的缓存行开始无效或者（可能）更大程度的风险 - 如果不完全 - 通过更大过程的其他步骤中的其他数据访问。 我在整个过程中执行的代码和访问的数据越多，任何相关的查找数据都将保留在缓存中的可能性越小（这可能与OP的情况有关，也可能不相关）。 要使用（my）哈希查找条目，您将遇到两个缓存未命中（一个用于加载索引的正确部分，另一个用于加载包含条目本身的区域），用于需要执行的每个比较。 在第一次尝试中找到一个条目将花费两个未命中，第二个尝试四个等等。在我的示例中，每个查找的60个时钟周期平均成本意味着该表可能完全驻留在L2高速缓存中并且L1不必去那里大部分案件。 我的x86-64 CPU有L1-3，RAM等待状态大约是4,10,40和100，这对我来说显示RAM完全被禁止而L3主要是。

第二个是代码缓存，如果它很小，紧凑，内联并且几乎没有控制传输（跳转和调用），它将产生更大的影响。 我的哈希例程可能完全驻留在L1代码缓存中。 对于更常见的情况，代码缓存行加载的数量越少，它就越快。

Answer 2

制作一组关键的val对结构。

按键对数组进行排序，将其作为静态数组放入程序中，只能是128kbyte。

然后在你的程序中，按键查找一个简单的二进制文件，平均只需要14次密钥比较才能找到正确的值。 在现代电脑上应该能够达到每秒3亿次仰视的速度。

您可以使用qsort进行排序并使用bsearch搜索std lib函数。

Answer 3

执行memonization，或简单地说，缓存已经计算过的值并计算新值。 您应该对输入进行散列并检查该结果的缓存。 您甚至可以从一组缓存值开始，您认为该函数将被更频繁地调用。 除此之外，我认为你不需要像其他答案所说的那样去任何极端。 做事简单，当您完成应用程序后，您可以使用分析工具查找瓶颈。

编辑：一些代码

 #include  #include  using namespace std; const int MAX_SIZE = 16000; int preCalcData[MAX_SIZE] = {}; int getPrecalculatedResult(int x){ return preCalcData[x]; } void setupPreCalcDataCache(){ for(int i = 0; i < MAX_SIZE; ++i){ preCalcData[i] = i*i; //or whatever calculation } } int main(){ setupPreCalcDataCache(); cout << getPrecalculatedResult(0) << endl; cout << getPrecalculatedResult(15999) << endl; return 0; } 

Answer 4

我不会太担心性能。 这个简单的例子，使用数组和二进制搜索lower_bound

 #include  #include  #include  #include  #include  const int N = 16000; typedef std::pair CALC; CALC calc[N]; static inline bool cmp_calcs(const CALC &c1, const CALC &c2) { return c1.first < c2.first; } int main(int argc, char **argv) { std::iostream::sync_with_stdio(false); for (int i = 0; i < N; ++i) calc[i] = std::make_pair(i, i); std::sort(&calc[0], &calc[N], cmp_calcs); for (long i = 0; i < 10000000; ++i) { int r = rand() % 16000; CALC *p = std::lower_bound(&calc[0], &calc[N], std::make_pair(r, 0), cmp_calcs); if (p->first == r) std::cout << "found\n"; } return 0; } 

并编译

 g++ -O2 example.cpp 

包括设置，在我5岁的PC上大约2秒内进行10,000,000次搜索。

Answer 5

您需要有效地存储16000个值，最好是在内存中。 我们假设这些值的计算比从存储中访问它们更耗时。

您可以使用许多不同的数据结构来完成工作，包括数据库。 If you access these values in queriable chunks, then the DB overhead may very well be absorbed and spread accross your processing.

You mentioned map and hashmap (or hashtable) already in your question tags, but these are probably not the best possible answers for your problem, although they could do a fair job, provided that the hashing function isn’t more expensive than the direct computation of the target UINT64 value, which has to be your reference benchmark.

• Van Emde Boas Trees
• Many variants of B-Trees (used extensively in database engines, high performance filesystems),
• 尝试

Are probably much better suited. Having some experience with it, I would probably go for a B-tree: they support fairly well serialization. That should let you prepare your dataset in advance in a different program. VEB trees have a very good access time (O(log log(n)), but I don’t know how easily they may be serialized.

Later on, if you need even more performance, it would also be interesting to know usage patterns of your “database” to figure out what caching techniques you could implement on top of the store.

Answer 6

Using std::pair is better than any of map for speed.

but if I were you, I firstly use a std::list to store the data, after I got them all, I move them into a simple vector, then retrieving goes very fast if you implement a simple binary tree search by yourself.