Google's B-tree挺快

#if 0
#include "set.h" // github.com/Kronuz/cpp-btree
using namespace btree;
#else
#include <set> // en.cppreference.com/w/cpp/container/multiset
#endif
#include <iostream>
using namespace std;

typedef multiset<int> S;
typedef S::const_iterator I;

int main() {
  S s;
  for (int i = 0; i < 1000000; i++) s.insert(i), s.insert(i + 10);
  cout << s.size() << endl;
  // g++ -x c++ /dev/null -dM -E
  // g++ -std=c++17 t.cpp
#if __cplusplus >= 201703
  const auto [a, b] = s.equal_range(12345);
#else
  pair<I,I> two = s.equal_range(12345);
  I a = two.first, b = two.second;
#endif
  for (auto p = a; p != b; p++) cout << *p << ' ';
  cout << endl; return 0;
}
// 我的电脑上都-Ofast, 分别是1秒和0.35秒。btree得-std=c+++17, std不必须。

Code... is based on Google's B-tree implementation. C++ B-tree is a template library that implements ordered in-memory containers based on a B-tree data structure. Similar to the STL std::map, std::set, std::multimap, and std::multiset templates, this library provides btree::map, btree::set, btree::multimap and btree::multiset... C++ B-tree containers have a few advantages compared with the standard containers, which are typically implemented using Red-Black trees.

B-tree - Detailed Pedia. The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems.

btree.h 3000多行。如果我被要求面试时写红黑树，我就拿出上面的例子，说：“我给你写个更高档的”——反正都写不出来，死得好看点。:-)

btree.h里有这么一段：

 *   btree_bench --benchmarks=. 2>&1 | ./benchmarks.awk
 *
 * Run on pmattis-warp.nyc (4 X 2200 MHz CPUs); 2010/03/04-15:23:06
 * Benchmark                 STL(ns) B-Tree(ns) @    <size>
 * --------------------------------------------------------
 * BM_set_int32_insert        1516      608  +59.89%  <256>    [40.0,  5.2]
 * BM_set_int32_lookup        1160      414  +64.31%  <256>    [40.0,  5.2]
 * BM_set_int32_fulllookup     960      410  +57.29%  <256>    [40.0,  4.4]
 * BM_set_int32_delete        1741      528  +69.67%  <256>    [40.0,  5.2]
 * BM_set_int32_queueaddrem   3078     1046  +66.02%  <256>    [40.0,  5.5]
 * BM_set_int32_mixedaddrem   3600     1384  +61.56%  <256>    [40.0,  5.3]
 * BM_set_int32_fifo           227      113  +50.22%  <256>    [40.0,  4.4]
 * BM_set_int32_fwditer        158       26  +83.54%  <256>    [40.0,  5.2]
 * BM_map_int32_insert        1551      636  +58.99%  <256>    [48.0, 10.5]
 * BM_map_int32_lookup        1200      508  +57.67%  <256>    [48.0, 10.5]
 * BM_map_int32_fulllookup     989      487  +50.76%  <256>    [48.0,  8.8]
 * BM_map_int32_delete        1794      628  +64.99%  <256>    [48.0, 10.5]
 * BM_map_int32_queueaddrem   3189     1266  +60.30%  <256>    [48.0, 11.6]
 * BM_map_int32_mixedaddrem   3822     1623  +57.54%  <256>    [48.0, 10.9]
 * BM_map_int32_fifo           151      134  +11.26%  <256>    [48.0,  8.8]
 * BM_map_int32_fwditer        161       32  +80.12%  <256>    [48.0, 10.5]
 * BM_set_int64_insert        1546      636  +58.86%  <256>    [40.0, 10.5]
 * BM_set_int64_lookup        1200      512  +57.33%  <256>    [40.0, 10.5]
 * BM_set_int64_fulllookup     971      487  +49.85%  <256>    [40.0,  8.8]
 * BM_set_int64_delete        1745      616  +64.70%  <256>    [40.0, 10.5]
 * BM_set_int64_queueaddrem   3163     1195  +62.22%  <256>    [40.0, 11.6]
 * BM_set_int64_mixedaddrem   3760     1564  +58.40%  <256>    [40.0, 10.9]
 * BM_set_int64_fifo           146      103  +29.45%  <256>    [40.0,  8.8]
 * BM_set_int64_fwditer        162       31  +80.86%  <256>    [40.0, 10.5]
 * BM_map_int64_insert        1551      720  +53.58%  <256>    [48.0, 20.7]
 * BM_map_int64_lookup        1214      612  +49.59%  <256>    [48.0, 20.7]
 * BM_map_int64_fulllookup     994      592  +40.44%  <256>    [48.0, 17.2]
 * BM_map_int64_delete        1778      764  +57.03%  <256>    [48.0, 20.7]
 * BM_map_int64_queueaddrem   3189     1547  +51.49%  <256>    [48.0, 20.9]
 * BM_map_int64_mixedaddrem   3779     1887  +50.07%  <256>    [48.0, 21.6]
 * BM_map_int64_fifo           147      145   +1.36%  <256>    [48.0, 17.2]
 * BM_map_int64_fwditer        162       41  +74.69%  <256>    [48.0, 20.7]
 * BM_set_string_insert       1989     1966   +1.16%  <256>    [64.0, 44.5]
 * BM_set_string_lookup       1709     1600   +6.38%  <256>    [64.0, 44.5]
 * BM_set_string_fulllookup   1573     1529   +2.80%  <256>    [64.0, 35.4]
 * BM_set_string_delete       2520     1920  +23.81%  <256>    [64.0, 44.5]
 * BM_set_string_queueaddrem  4706     4309   +8.44%  <256>    [64.0, 48.3]
 * BM_set_string_mixedaddrem  5080     4654   +8.39%  <256>    [64.0, 46.7]
 * BM_set_string_fifo          318      512  -61.01%  <256>    [64.0, 35.4]
 * BM_set_string_fwditer       182       93  +48.90%  <256>    [64.0, 44.5]
 * BM_map_string_insert       2600     2227  +14.35%  <256>    [72.0, 55.8]
 * BM_map_string_lookup       2068     1730  +16.34%  <256>    [72.0, 55.8]
 * BM_map_string_fulllookup   1859     1618  +12.96%  <256>    [72.0, 44.0]
 * BM_map_string_delete       3168     2080  +34.34%  <256>    [72.0, 55.8]
 * BM_map_string_queueaddrem  5840     4701  +19.50%  <256>    [72.0, 59.4]
 * BM_map_string_mixedaddrem  6400     5200  +18.75%  <256>    [72.0, 57.8]
 * BM_map_string_fifo          398      596  -49.75%  <256>    [72.0, 44.0]
 * BM_map_string_fwditer       243      113  +53.50%  <256>    [72.0, 55.8]