SQLite B 樹實現(xiàn)代碼

2024-09-07 00:10:01

字體：大中小

供稿：網(wǎng)友

這個結(jié)構(gòu)一般用于數(shù)據(jù)庫的索引，綜合效率非常高，像 Berkerly DB , sqlite , mysql 數(shù)據(jù)庫都使用了這個算法處理索引。
如果想自己做個小型數(shù)據(jù)庫，可能參考一下這個算法的實現(xiàn)，可能會對你有所幫助。

其中的注冊很詳細，不用再多說了。

/*btrees.h*/
/*
*平衡多路樹的一種重要方案。
*在1970年由R.Bayer和E.McCreight發(fā)明。
*/
#defineM1
/*B樹的階，即非根節(jié)點中鍵的最小數(shù)目。
*有些人把階定義為非根節(jié)點中子樹的最大數(shù)目。
*/
typedefinttypekey;
typedefstructbtnode{/*B-Tree節(jié)點*/
intd;/*節(jié)點中鍵的數(shù)目*/
typekeyk[2*M];/*鍵*/
char*v[2*M];/*值*/
structbtnode*p[2*M 1];/*指向子樹的指針*/
}node,*btree;
/*
*每個鍵的左子樹中的所有的鍵都小于這個鍵，
*每個鍵的右子樹中的所有的鍵都大于等于這個鍵。
*葉子節(jié)點中的每個鍵都沒有子樹。
*/

/*當M等于1時也稱為2-3樹
* ---- ----
*|k0|k1|
* - ---- ---- ---
*|p0|p1|p2|
* ---- ---- ----
*/
externintbtree_disp;/*查找時找到的鍵在節(jié)點中的位置*/
externchar*

上一篇：開源嵌入式數(shù)據(jù)庫Bericeley DB和SQLite

下一篇：為SQLite數(shù)據(jù)庫添加加密功能