Manpages

名 前

btree − btree デ ー タ ベ ー ス へ の ア ク セ ス メ ソ ッ ド

書 式

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

説 明

大 事 な 注 意 : こ の ペ ー ジ は 、 バ ー ジ ョ ン 2.1 ま で の glibc が 提 供 す る イ ン タ ー フ ェ ー ス に つ い て 説 明 し て い る 。 バ ー ジ ョ ン 2.2 以 降 の glibc で は 、 も は や こ れ ら の イ ン タ ー フ ェ ー ス は 提 供 さ れ て い な い 。 お そ ら く 、 こ の ペ ー ジ で は な く 、 libdb ラ イ ブ ラ リ が 提 供 す る API を お 探 し な の だ ろ う 。 ル ー チ ン dbopen(3) は デ ー タ ベ ー ス フ ァ イ ル に 対 す る ラ イ ブ ラ リ イ ン タ ー フ ェ ー ス で あ る 。 サ ポ ー ト さ れ て い る フ ァ イ ル フ ォ ー マ ッ ト の ひ と つ に btree フ ァ イ ル が あ る 。 デ ー タ ベ ー ス へ の ア ク セ ス メ ソ ッ ド に 関 す る 一 般 的 な 記 述 は dbopen(3) に 書 か れ て い る 。 こ の マ ニ ュ ア ル ペ ー ジ で は btree 特 有 の 情 報 に つ い て の み 記 述 す る 。

btree デ ー タ 構 造 で は 、 ソ ー ト さ れ た バ ラ ン ス ツ リ ー 構 造 に 互 い に 関 連 づ け ら れ た キ ー /デ ー タ 対 を 格 納 し て い る 。

dbopen(3) に 渡 さ れ る btree ア ク セ ス メ ソ ッ ド に 特 有 の デ ー タ 構 造 体 は 、 <db.h> イ ン ク ル ー ド フ ァ イ ル で 次 の よ う に 定 義 さ れ て い る 。

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

flags の 値 は 以 下 の 値 の 論 理 和 で 指 定 さ れ る 。

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 バ イ ト で 、 最 大 値 は 64K で あ る 。 psize が 0 (ペ ー ジ サ イ ズ が 指 定 さ れ て い な い ) の 場 合 、 フ ァ イ ル シ ス テ ム の I/O ブ ロ ッ ク サ イ ズ に 基 づ い て 決 め ら れ る 。

compare

compare は キ ー の 比 較 関 数 で あ る 。 最 初 の キ ー 引 数 に 対 し 、 二 番 目 の キ ー 引 数 が 大 き い 場 合 に は 正 の 整 数 を 、 同 じ 場 合 に は ゼ ロ を 、 小 さ い 場 合 に は 負 の 整 数 を 返 す 。 ツ リ ー を 開 く 際 に は 、 常 に 同 じ 比 較 関 数 が 使 わ れ な け れ ば な ら な い 。 compare が NULL (比 較 関 数 が 指 定 さ れ て い な い ) の 場 合 、 辞 書 的 に 比 較 さ れ る 。 短 い キ ー は 長 い キ ー よ り 小 さ い こ と に な る 。

prefix

prefix は 前 置 比 較 関 数 で あ る 。 こ の ル ー チ ン は (指 定 さ れ た 場 合 に は )、 二 番 目 の キ ー 引 数 の バ イ ト 数 を 返 さ な く て は な ら な い 。 こ れ は 二 番 目 の キ ー 引 数 が 一 番 目 の キ ー 引 数 よ り 大 き い か ど う か 決 め る の に 必 要 で あ る 。 キ ー が 同 じ 場 合 、 キ ー の 長 さ が 返 る 。 こ の ル ー チ ン が 有 用 か ど う か は 、 デ ー タ に 強 く 依 存 す る 。 し か し デ ー タ セ ッ ト に よ っ て は 、 明 ら か に ツ リ ー の サ イ ズ と 検 索 時 間 を 減 ら し て く れ る 。 prefix が NULL (prefix 関 数 が 指 定 さ れ て い な い ) で 、 か つ 比 較 関 数 が 指 定 さ れ て い な い と 、 デ フ ォ ル ト の 辞 書 比 較 ル ー チ ン が 使 わ れ る 。 prefix が NULL で 比 較 関 数 が 指 定 さ れ て い る 場 合 は 、 前 置 比 較 は 行 わ れ な い 。

lorder

デ ー タ ベ ー ス に 格 納 さ れ て い る メ タ デ ー タ の 整 数 値 の バ イ ト オ ー ダ ー 。 こ の 数 字 は 、 順 序 を 整 数 で 表 し た も の で あ る 。 例 え ば ビ ッ グ エ ン デ ィ ア ン な ら 、 こ の 数 値 は 4,321 と な る 。 lorder が 0 (指 定 さ れ て い な い ) の 場 合 、 現 在 の ホ ス ト で 使 わ れ て い る バ イ ト オ ー ダ ー が 使 わ れ る 。 フ ァ イ ル が 既 に 存 在 し て い る (ま た は O_TRUCT フ ラ グ が 指 定 さ れ て い な い ) と 、 引 き 数 flag, lorder, psize に 指 定 さ れ た 値 は 無 視 さ れ 、 ツ リ ー が 作 ら れ た 時 に 使 っ た 値 が 用 い ら れ る 。 ツ リ ー の 前 方 順 検 索 は 、 最 小 キ ー か ら 最 大 キ ー に 向 か っ て 行 わ れ る 。 ツ リ ー か ら キ ー /デ ー タ 対 が 削 除 さ れ る こ と に よ っ て で き た ス ペ ー ス は 、 通 常 再 利 用 で き る 形 に な っ て い る が 再 利 用 さ れ る こ と は 無 い 。 つ ま り brtee 記 憶 構 造 は 肥 大 す る 一 方 で あ る 。 対 策 は 過 度 の 削 除 を 避 け る か 、 存 在 す る ツ リ ー を 調 べ て 定 期 的 に 新 し い ツ リ ー を 作 る か 、 だ け で あ る 。

Searches, insertions, and deletions in a btree will all complete in O lg base N where base is the average fill factor. Often, inserting ordered data into btrees results in a low fill factor. This implementation has been modified to make ordered insertion the best case, resulting in a much better than normal page fill factor.

エ ラ ー

btree ア ク セ ス メ ソ ッ ド ル ー チ ン は 失 敗 す る と 、 ラ イ ブ ラ リ ル ー チ ン dbopen(3) で 定 義 さ れ て い る エ ラ ー の い ず れ か を errno と し て 返 す 。

バ グ

バ イ ト オ ー ダ ー と し て は ビ ッ グ エ ン デ ィ ア ン と リ ト ル エ ン デ ィ ア ン の み が サ ポ ー ト さ れ て い る 。

関 連 項 目

dbopen(3), hash(3), mpool(3), recno(3)

The Ubiquitous B−tree, Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121−138.

Prefix B−trees, Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11−26.

The Art of Computer Programming Vol. 3: Sorting and Searching, D.E. Knuth, 1968, pp 471−480.

こ の 文 書 に つ い て

こ の man ペ ー ジ は Linux man−pages プ ロ ジ ェ ク ト の リ リ ー ス 3.79 の 一 部 で あ る 。 プ ロ ジ ェ ク ト の 説 明 と バ グ 報 告 に 関 す る 情 報 は http://www.kernel.org/doc/man−pages/ に 書 か れ て い る 。