BUGS

仅支持大小端字节顺序。

语法

#include <sys/types.h>
#include <db.h>

出版信息

这个页面是Linux手册页项目5.08版的一部分。有关项目的说明、有关报告错误的信息以及此页面的最新版本，请访问https://www.kernel.org/doc/man-pages/。

名称

btree-btree数据库访问方法

另外参见

dbopen(3)，hash(3)，mpool(3)，recno(3)

无处不在的B树，Douglas Comer，ACM Comput。生存11，2(1979年6月)121-138。

前缀B树，Bayer和Unterauer，数据库系统上的ACM事务，第1卷。 2，1(1977年3月)，11-26。

计算机编程艺术卷。 3：排序和搜索D.E. Knuth，1968年，第471-480页。

说明

请注意：此页面记录了glibc所提供的接口，直至2.1版。从2.2版开始，glibc不再提供这些接口。可能您正在寻找libdb库提供的API。

例程dbopen(3)是数据库文件的库接口。支持的文件格式之一是btree文件。数据库访问方法的一般说明在dbopen(3)中，此手册页仅描述特定于btree的信息。

btree数据结构是一种排序的，平衡的树结构，用于存储关联的键/数据对。

提供给dbopen(3)的特定于btree访问方法的数据结构在包含文件中定义如下：

typedef struct {
    unsigned long flags;
    unsigned int  cachesize;
    int           maxkeypage;
    int           minkeypage;
    unsigned int  psize;
    int         (*compare)(const DBT *key1, const DBT *key2);
    size_t      (*prefix)(const DBT *key1, const DBT *key2);
    int           lorder;
} BTREEINFO;

此结构的元素如下：

flags

The flag value is specified by ORing any of the following values:

R_DUP

允许树中有重复的密钥，也就是说，如果要插入的密钥已经在树中，则允许插入。如dbopen(3)中所述，缺省行为是在插入新密钥时覆盖匹配的密钥，或者如果指定了R_NOOVERWRITE标志则失败。 R_DUP标志被R_NOOVERWRITE标志覆盖，如果指定了R_NOOVERWRITE标志，则尝试将重复的键插入树中将失败。

如果数据库包含重复的键，则在使用get例程的情况下，键/数据对的检索顺序是不确定的，但是，设置了R_CURSOR标志的seq例程调用将始终返回任何重复键组的逻辑"第一"。

cachesize

建议的内存缓存最大大小(以字节为单位)。此值仅供参考，访问方法将分配更多的内存，而不是失败。由于每次搜索都会检查树的根页面，因此缓存最近使用的页面会大大缩短访问时间。此外，物理写入会尽可能延迟，因此适度的缓存可以显着减少I / O操作的数量。显然，如果在修改树时系统崩溃，则使用缓存会增加(但只会增加)损坏或丢失数据的可能性。如果cachesize为0(未指定大小)，则使用默认缓存。

maxkeypage

将在任何单个页面上存储的最大密钥数。目前尚未实现。

minkeypage

将存储在任何单个页面上的最小键数。此值用于确定哪些密钥将存储在溢出页面上，也就是说，如果某个密钥或数据项的长度大于页面大小除以minkeypage值，则它将存储在溢出页面上而不是页面本身。如果minkeypage为0(未指定最小键数)，则使用值2。

psize

页面大小是用于树中节点的页面大小(以字节为单位)。最小页面大小为512字节，最大页面大小为64 KB。如果psize为0(未指定页面大小)，则根据基础文件系统I / O块大小选择页面大小。

compare

比较是关键的比较功能。如果认为第一个键参数分别小于，等于或大于第二个键参数，则它必须返回小于，等于或大于零的整数。每次打开给定树时，都必须在同一个树上使用相同的比较功能。如果compare为NULL(未指定比较功能)，则按词法对键进行比较，认为较短的键小于较长的键。

prefix

前缀是前缀比较功能。如果已指定，则此例程必须返回确定第二个密钥自变量大于第一个密钥自变量所必需的字节数。如果密钥相等，则应返回密钥长度。请注意，此例程的有用性与数据密切相关，但是在某些数据集中可以显着减少树的大小和缩短搜索时间。如果prefix为NULL(未指定前缀功能)，并且未指定比较功能，则使用默认的词法比较例程。如果prefix为NULL并且指定了比较例程，则不进行前缀比较。

lorder

存储的数据库元数据中整数的字节顺序。该数字应将订单表示为整数；例如，大端顺序为4,321。如果lorder为0(未指定顺序)，则使用当前主机顺序。

如果文件已经存在(并且未指定O_TRUNC标志)，则将忽略为参数标志lorder和psize指定的值，而使用创建树时使用的值。

对树的前向顺序扫描是从最小键到最大键。

从树中删除键/数据对释放的空间永远不会被回收，尽管通常可以重复使用。这意味着btree存储结构是仅增长的。唯一的解决方案是避免过多的删除，或者从对现有树的扫描中定期创建一棵新树。

btree中的搜索，插入和删除都将在O lg base N中完成，其中base是平均填充因子。通常，将有序数据插入btree会导致填充系数较低。已修改此实现，以使有序插入成为最佳情况，从而导致比正常页面填充因子好得多。

Linux程序员手册 第3部分
更新日期： 2017-09-15

错误说明

btree访问方法例程可能会失败，并为库例程dbopen(3)指定的任何错误设置errno。