BTREE

̾Á°

½ñ¼°

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

ÀâÌÀ

btree ¥Ç¡¼¥¿¹½Â¤¤Ç¤Ï¡¢¥½¡¼¥È¤µ¤ì¤¿¥Ð¥é¥ó¥¹¥Ä¥ê¡¼¹½Â¤¤Ë ¸ß¤¤¤Ë´ØÏ¢¤Å¤±¤é¤ì¤¿¥­¡¼/¥Ç¡¼¥¿ÂФò³ÊǼ¤·¤Æ¤¤¤ë¡£

dbopen ¤ËÅϤµ¤ì¤ë btree ¥¢¥¯¥»¥¹¥á¥½¥Ã¥É¤ËÆÃÍ­¤Î¥Ç¡¼¥¿¹½Â¤ÂΤϡ¢ <db.h> ¥¤¥ó¥¯¥ë¡¼¥É¥Õ¥¡¥¤¥ë¤Ç¼¡¤Î¤è¤¦¤ËÄêµÁ¤µ¤ì¤Æ¤¤¤ë¡£

typedef struct {

u_long flags;
u_int cachesize;
int maxkeypage;
int minkeypage;
u_int psize;
int (*compare)(const DBT *key1, const DBT *key2);
size_t (*prefix)(const DBT *key1, const DBT *key2);
int lorder;

¤³¤Î¹½Â¤ÂΤÎÍ×ÁǤò°Ê²¼¤Ë¼¨¤¹¡£

flags

flag ¤ÎÃÍ¤Ï °Ê²¼¤ÎÃͤΤ¤¤º¤ì¤«¤«¡¢¤³¤ì¤é¤ÎÏÀÍýϤǻØÄꤵ¤ì¤ë¡£

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

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 µ­²±¹½Â¤¤ÏÈîÂ礹¤ë°ìÊý¤Ç¤¢¤ë¡£ Âкö¤Ï²áÅ٤κï½ü¤òÈò¤±¤ë¤«¡¢ ¸ºß¤¹¤ë¥Ä¥ê¡¼¤òÄ´¤Ù¤ÆÄê´üŪ¤Ë¿·¤·¤¤¥Ä¥ê¡¼¤òºî¤ë¤«¡¢¤À¤±¤Ç¤¢¤ë¡£

¥¨¥é¡¼

´ØÏ¢¹àÌÜ

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.  

¥Ð¥°

Index

̾Á°

½ñ¼°

ÀâÌÀ

¥¨¥é¡¼

´ØÏ¢¹àÌÜ

¥Ð¥°