Kyoto Cabinet

Qter

KC是一个数据库管理的 lib，是 Tokyo Cabinet 的改进版本。数据库是一个简单的包含记录的数据文件，每个记录是一个键值对（key/value），key和value都是变长的字节序列。key和 value既可以是二进制的，也可以是文本字符串。数据库中的key必须唯一。数据库既没有表的概念，也不存在数据类型。所有的记录被组织为hash表或 B+树。

在数据库中，可以储存key-value记录，也可以根据key来获取和删除记录。还可以遍历访问所有的key。这些方法类似于UNIX标准中的DBM库（及后来的NDBM和GDBM）。因为KC的高性能，可以作为DBM的替代品。

Hash 数据库 的每个操作的时间复杂度是 O(1)，因此理论上，性能是常量而与数据库的规模无关。在实践中，性能由内存或存储设备的速度决定。如果数据库的大小小于内存大小，性能表现为内存的速 度，比STL中的std::map要快。当然数据库大小可以大于内存大小，最大上限是8EB（1024×1024×1024GB）。即使在这样的情况下， 每个操作也只需要一两个存储设备的seek操作。

B+ tree 数据库的每个操作的时间复杂度是 O(log N)。因此理论上，性能是数据库规模的对数。尽管B+ tree 数据库的随机访问性能要慢于 hash数据库，但B+ tree数据库支持对 key 顺序的连续访问，这可以实现对字符串的前向匹配查找和整数的范围查找。连续访问的性能远快于随机访问。

API是基于面向对象设计的，hash数据库和B+ tree数据库都有从同一个超类继承而来的同样的方法。除了他们，还有7种数据库也继承了同样的超类。prototype hash 数据库采用标准容器 std::unordered_map 实现，prototype tree 数据库采用标准容器 std::map 实现，stash 数据库是采用naive hash map的原始实现来节省内存，cache hash 数据库是采用 LRU删除算法的双向链接 hash map 原始实现。cache tree 数据库是基于cache hash 数据库并提供B+ tree的机制。directory hash 数据库是采用文件系统的目录机制实现，每个记录存储为一个目录下的文件。directory tree 数据库基于directory hash数据库并提供B+ tree的机制。所有的数据库都有相关的事物（transaction）和游标（cursor）的实用方法。软件也包含了命令行接口的程序。

KC的运行速度非常快。例如，保存一百万记录到hash数据库中只需要0.9秒，保存到B+ tree数据库只需要1.1秒。而且数据库本身还非常小。例如，hash数据库的每个记录头只有16字节，B+ tree数据库是4字节。更进一步，KC的伸缩性非常大，数据库大小可以增长到8EB（9.22e18 bytes）。

KC是C++语言编写的，并提供C++、C、Java、Python、Ruby、Perl 和 Lua 的API。KC可以用在所有符合 C++03标准并带TR1库扩展的平台。KC是GNU General Public License的自由软件。FOSS License例外也提供用来适应其它免费和开源的licenses。另一方面也提供商业license。如果你在专有软件中使用KC，那么你需要商业 license。