为什么文件索引要使用B-tree
实际上文件索引的数据结构无非就是 B树 和 B+树，但实际上在内存中也可以应用这种数据结构，但是意义不大，因为这种结构就是为文件存储设计的，为了减少磁盘IO，加速查找，那为什么要使用这两种数据结构呢，第一 这是树形结构，所以在保存的时候可以按照有序的规则去储存索引信息，第二 这个树形结构每一个节点可以保存多个关键字也就是相当于可以存储多个索引，这样的话一次I/O就会尽可能多的知道下一步的位置及当前是否命中索引.
为什么把索引存储在文件中
想想如果数据量很大， 内存的大小是有限的，所以无法一直把索引信息存储在内存中，而且随时有断电数据丢失的风险，所以就需要把索引数据落在磁盘文件中，但这时候就需要一种高效的算法结构来管理，所以这种数据结构就诞生了，而且数据库底层索引结构都是 B+,B 来管理.
B+ 和 B 树区别
B+树只有叶节点存放数据， 并且每一个数据都被链表链接，可实现遍历、范围查找等功能，剩下其余节点用来索引，而B树是每个索引节点都会有Data域
B+和B树的区别-（本图来自网络）
如何选择
像 Mysql 都是用 B+ 来实现的， 因为更方便合适， 因为总会存在范围查找、分页等相关功能，正好 B+ 这种结构可以满足，同时还有一点就是因为 B+ 所有的数据都在叶子节点，这就导致索引节点相对比较小，每次IO的数量更多，起到减少IO次数作用， 而像 Mongodb 这种就是使用 B树来实现的， 因为它是 Key、value 数据库，对B+提供的特性需求使用不是很强烈，而且B树的数据在每个节点都有保存，所以单次查找速度理论会更快，因为不需要查找到最后一层叶子节点才会找到数据，当然实际效率具体分情况，没有最好的结构，只有最合适的结构.
B 树的基本特性
(1) 所有节点的孩子节点数中的最大值称为B树的阶，设为 M
(2) 根结点的儿子数为[2, M]
(3) 除根结点以外的非叶子结点的儿子数为[M/2, M]
(4) 每个结点存放至少M/2(取上整)-1 和至多M-1个关键字
(5) 非叶子结点的关键字：K[1], K[2], …, K[m-1]，m<M+1；且K[i]< K[i+1]
(6) 非叶子结点的指针：P[1], P[2], …, P[m]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树
如何把B-Tree储存文件中
我们都知道在内存中维护一颗树，是比较简单的，只需要记住每个节点的指针即可，但是我们要在文件中维护这么一颗树该怎么办，其实道理是一样的，内存中有指针，但文件中有偏移量，所以我们可以用偏移量也就是数据所在文件中的位置来记录每一个Node节点，文件偏移量 == 内存指针， 但有一点要知道，无论内存还是文件都需要有一个头结点来指向第一个Node节点，但是文件涉及到打开和关闭，不像内存只需要一个头指针变量保存即可，所以每次在打开文件的时候，我们都要知道这个头节点在哪里，基于这个所以要额外记录一个文件头FileHeadNode节点，用来指向文件中的第一个Node结点，这个文件头节点固定存储在文件的起始位置，每次打开文件首先先读取文件头节点即可.
设计存储结构
/* 数据结构体 */
typedef struct {
sint len; // 数据长度
uint pos; // 数据位置
} _data;
/* 文件头结构体 */
typedef struct {
uint head; // 头结点位置
uint node; // 节点数目
} FileHead;
/* 索引节点结构体 */
typedef struct {
sint keyNum; // 关键字数量
uint parent; // 父节点
uint key[M + 1]; // 关键字也就是索引值
uint ptr[M + 1]; // 儿子节点位置
_data data[M + 1]; // 数据信息
} BTNode;
上面说的
_data数据结构特别说明下， 这个结构记录数据的位置和长度，因为数据是单独存储在一个文件里面，没有一起存储在索引文件中.
文件存储结构图
文件存储结构图
举个栗子
我们将如下一组Id对应的数据存入B树：
设 B-Tree （M=3） 阶
[97 => data1 100 => data2 101 => data3 98 => data4 99 => data5 102 => data6 103 => data7]
B-Tree
可以看到最终生成的B-Tree结构应该如上图，当然根据设定的3阶B树，中间会经历4次分裂2次建根，这里就不一步一步描述了，最后会生成7个节点， 根节点是 100 这个索引id
把这颗（三阶三层B树）写到文件中
源码在最后
写入
// a.out id 索引ID，存储字符串
./a.out id 97 data1
./a.out id 100 data2
./a.out id 101 data3
./a.out id 98 data4
./a.out id 99 jkhjjjss
./a.out id 102 fffdds
./a.out id 103 helloaaa
查看
./a.out show
-------------------Head(0)-------------------------
FileHead_size:8----BTNode_size:72-----head_pos:440----node_num:7
-------------------Node(1)-------------------------
index_ptr=440, parent=0, offset=0, keyNum=1, key=0, ptr=152, data.len=0, data.pos=0
index_ptr=440, parent=0, offset=1, keyNum=1, key=100, ptr=368, data.len=12, data.pos=12
-------------------Node(2)-------------------------
index_ptr=152, parent=440, offset=0, keyNum=1, key=0, ptr=8, data.len=0, data.pos=0
index_ptr=152, parent=440, offset=1, keyNum=1, key=98, ptr=224, data.len=12, data.pos=36
-------------------Node(3)-------------------------
index_ptr=368, parent=440, offset=0, keyNum=1, key=0, ptr=80, data.len=0, data.pos=0
index_ptr=368, parent=440, offset=1, keyNum=1, key=102, ptr=296, data.len=12, data.pos=60
-------------------Node(4)-------------------------
index_ptr=8, parent=152, offset=0, keyNum=1, key=0, ptr=0, data.len=0, data.pos=0
index_ptr=8, parent=152, offset=1, keyNum=1, key=97, ptr=0, data.len=12, data.pos=0
-------------------Node(5)-------------------------
index_ptr=224, parent=152, offset=0, keyNum=1, key=0, ptr=0, data.len=0, data.pos=0
index_ptr=224, parent=152, offset=1, keyNum=1, key=99, ptr=0, data.len=12, data.pos=48
-------------------Node(6)-------------------------
index_ptr=80, parent=368, offset=0, keyNum=1, key=0, ptr=0, data.len=0, data.pos=0
index_ptr=80, parent=368, offset=1, keyNum=1, key=101, ptr=0, data.len=12, data.pos=24
-------------------Node(7)-------------------------
index_ptr=296, parent=368, offset=0, keyNum=1, key=0, ptr=0, data.len=0, data.pos=0
index_ptr=296, parent=368, offset=1, keyNum=1, key=103, ptr=0, data.len=5, data.pos=72
输出参数说明
/* Head */
FileHead_size: 文件头节点，固定8字节
BTNode_size: 索引节点，固定72字节，根据M阶数定义的大小去调整
head_pos: 头结点位置
node_num: 索引节点数量
/* Node */
index_ptr: 当前节点位置
parent: 父节点位置
keyNum: 索引数量
key: 索引值
ptr: 儿子节点位置
data.len: 数据存储长度
data.pos: 数据文件中的位置
通过输出结果可以看到， 这些索引数据的关联关系已经完整的打印出来了， 通过文件中的偏移位置来记录层级关系，如下图
文件 B-Tree
源码如下
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define M 3 // 设定3阶B-Tree
#define QUANEUE_LEN 100
#define INDEX_FILE_NAME "index_btree"
#define DATA_FILE_NAME "data_file"
#define MALLOC_NODE( p, type ) type * p = (type *) malloc( sizeof(type) ); memset( p, 0, sizeof(type) )
#define FREE_NODE( p ) free( p )
#define FSEEK_END_WRITE( fp, pos, buf, size ) fseek( fp, 0, SEEK_END ); pos = ftell( fp ); fwrite( buf, size, 1, fp )
#define FSEEK_HED_WRITE( fp, pos, buf, size ) fseek( fp, 0, SEEK_SET ); pos = ftell( fp ); fwrite( buf, size, 1, fp )
#define FSEEK_FIXED_READ( fp, pos, buf, size ) fseek( fp, pos, SEEK_SET ); fread( buf, size, 1, fp )
#define FSEEK_FIXED_WRITE( fp, pos, buf, size ) fseek( fp, pos, SEEK_SET ); fwrite( buf, size, 1, fp )
#define OPEN_FILE( file_name, mode ) fopen( file_name, mode )
#define OPEN_FILE_READ( file_name, mode, buf, size ) fp = OPEN_FILE( file_name, mode ); fread( buf, size, 1, fp )
#define OPEN_FILE_WRITE( file_name, mode, buf, size ) fp = OPEN_FILE( file_name, mode ); fwrite( buf, size, 1, fp )
#define CLOSE_FILE( fp ) fclose( fp )
typedef unsigned int uint;
typedef unsigned short int sint;
typedef FILE * file;
typedef struct {
sint len;
uint pos;
} _data;
typedef struct {
uint head;
uint node;
} FileHead;
typedef struct {
sint keyNum;
uint parent;
uint key[M + 1];
uint ptr[M + 1];
_data data[M + 1];
} BTNode;
typedef struct {
uint pt; /* 指向找到的结点位置 */
sint i; /* 1..m，在结点中的关键字序号 */
sint tag; /* 1:查找成功，0:查找失败 */
} Result;
static file fp;
/************ B树查找相关方法 *************/
static int Search( BTNode* NodeBuf, uint key )
{
sint i = 1;
while ( i <= NodeBuf->keyNum && key > NodeBuf->key[i] )
{
i++;
}
return(i);
}
static void SearchBTree( uint node_pos, uint key, Result* r )
{
sint i = 0;
sint found = 0;
uint parent_pos = 0;
MALLOC_NODE( NodeBuf, BTNode );
while ( node_pos != 0 && found == 0 )
{
FSEEK_FIXED_READ( fp, node_pos, NodeBuf, sizeof(BTNode) );
i = Search( NodeBuf, key );
if ( i <= NodeBuf->keyNum && NodeBuf->key[i] == key )
{
found = 1;
} else {
parent_pos = node_pos;
node_pos = NodeBuf->ptr[i - 1]; /* 指针下移 */
}
}
if ( 1 == found ) /* 查找成功，返回key的位置node_pos和i */
{
r->pt = node_pos;
r->i = i;
r->tag = 1;
} else { /* 查找失败，返回key的插入位置parent_pos和i */
r->pt = parent_pos;
r->i = i;
r->tag = 0;
}
FREE_NODE( NodeBuf );
}
/************ B树插入相关方法 *************/
static void upFileHead( uint new_head_pos )
{
MALLOC_NODE( fileHeadBuf, FileHead );
FSEEK_FIXED_READ( fp, 0, fileHeadBuf, sizeof(FileHead) );
if ( new_head_pos > 0 )
{
fileHeadBuf->head = new_head_pos;
}
fileHeadBuf->node++;
FSEEK_FIXED_WRITE( fp, 0, fileHeadBuf, sizeof(FileHead) );
FREE_NODE( fileHeadBuf );
}
static void newRoot( uint head_pos, uint key, _data data, uint ap )
{
uint pos;
MALLOC_NODE( rootNodeBuf, BTNode );
rootNodeBuf->keyNum = 1;
rootNodeBuf->ptr[0] = head_pos;
rootNodeBuf->ptr[1] = ap;
rootNodeBuf->key[1] = key;
rootNodeBuf->data[1] = data;
FSEEK_END_WRITE( fp, pos, rootNodeBuf, sizeof(BTNode) );
/* 读取原根结点更新parent位置 */
FSEEK_FIXED_READ( fp, head_pos, rootNodeBuf, sizeof(BTNode) );
rootNodeBuf->parent = pos;
FSEEK_FIXED_WRITE( fp, head_pos, rootNodeBuf, sizeof(BTNode) );
/* 读取分裂结点更新parent位置 */
FSEEK_FIXED_READ( fp, ap, rootNodeBuf, sizeof(BTNode) );
rootNodeBuf->parent = pos;
FSEEK_FIXED_WRITE( fp, ap, rootNodeBuf, sizeof(BTNode) );
/* 更新文件头 */
upFileHead( pos );
FREE_NODE( rootNodeBuf );
}
static uint split( BTNode* NodeBuf, uint node_pos, sint s )
{
sint i, j;
sint n = NodeBuf->keyNum;
uint ap;
MALLOC_NODE( apNodeBuf, BTNode );
MALLOC_NODE( apNodeBufChild, BTNode );
apNodeBuf->ptr[0] = NodeBuf->ptr[s];
for ( i = s + 1, j = 1; i <= n; i++, j++ )
{
apNodeBuf->key[j] = NodeBuf->key[i];
apNodeBuf->ptr[j] = NodeBuf->ptr[i];
apNodeBuf->data[j] = NodeBuf->data[i];
}
apNodeBuf->keyNum = n - s;
apNodeBuf->parent = NodeBuf->parent;
FSEEK_END_WRITE( fp, ap, apNodeBuf, sizeof(BTNode) );
/* 更新文件头结点数量 */
upFileHead( 0 );
for ( i = 0; i <= n - s; i++ )
{
/* 修改新结点的子结点的parent域 */
if ( apNodeBuf->ptr[i] != 0 )
{
FSEEK_FIXED_READ( fp, apNodeBuf->ptr[i], apNodeBufChild, sizeof(BTNode) );
apNodeBufChild->parent = ap;
FSEEK_FIXED_WRITE( fp, apNodeBuf->ptr[i], apNodeBufChild, sizeof(BTNode) );
}
}
FSEEK_FIXED_READ( fp, node_pos, NodeBuf, sizeof(BTNode) );
NodeBuf->keyNum = s - 1; /* 修改NodeBuf结点的关键字数量 */
FSEEK_FIXED_WRITE( fp, node_pos, NodeBuf, sizeof(BTNode) );
FREE_NODE( apNodeBuf );
FREE_NODE( apNodeBufChild );
return(ap);
}
static BTNode Insert( uint node_pos, sint i, uint key, uint ap, _data data )
{
BTNode buf;
BTNode * NodeBuf = &buf;
/* 读取节点 */
FSEEK_FIXED_READ( fp, node_pos, NodeBuf, sizeof(BTNode) );
sint j;
for ( j = NodeBuf->keyNum; j >= i; j-- )
{
/* 后移 */
NodeBuf->key[j + 1] = NodeBuf->key[j];
NodeBuf->ptr[j + 1] = NodeBuf->ptr[j];
NodeBuf->data[j + 1] = NodeBuf->data[j];
}
NodeBuf->key[i] = key;
NodeBuf->ptr[i] = ap;
NodeBuf->data[i] = data;
NodeBuf->keyNum++;
FSEEK_FIXED_WRITE( fp, node_pos, NodeBuf, sizeof(BTNode) );
return(*NodeBuf);
}
static void InsertBTree( uint head_pos, uint key, uint node_pos, sint i, _data data )
{
sint s = 0;
sint finished = 0;
sint needNewRoot = 0;
uint ap = 0;
BTNode NodeBuf;
Result res;
while ( 0 == needNewRoot && 0 == finished )
{
NodeBuf = Insert( node_pos, i, key, ap, data );
if ( NodeBuf.keyNum < M )
{
finished = 1;
} else {
/* 得到中间结点位置 */
s = (M + 1) / 2;
/* 分裂结点 */
ap = split( &NodeBuf, node_pos, s );
key = NodeBuf.key[s];
data = NodeBuf.data[s];
/* 在双亲位置插入关键字 */
if ( NodeBuf.parent != 0 )
{
/* 寻找插入的位置 */
node_pos = NodeBuf.parent;
FSEEK_FIXED_READ( fp, node_pos, &NodeBuf, sizeof(BTNode) );
i = Search( &NodeBuf, key );
printf( "split--%u, ap--%u, key--%u, i=%d \n", NodeBuf.parent, ap, key, i );
} else {
needNewRoot = 1;
}
}
}
if ( 1 == needNewRoot )
{
newRoot( head_pos, key, data, ap );
}
}
/************ 公共方法 *************/
static void createInitFile()
{
sint node_pos;
FileHead head;
BTNode node;
/* 创建索引文件 */
if ( OPEN_FILE( INDEX_FILE_NAME, "rb" ) == NULL )
{
fp = OPEN_FILE( INDEX_FILE_NAME, "wb+" );
/* 初始化Head */
FileHead head = { 0, 1 };
FSEEK_END_WRITE( fp, node_pos, (char *) &head, sizeof(head) );
/* 初始化Node */
BTNode node = { 0 };
FSEEK_END_WRITE( fp, node_pos, (char *) &node, sizeof(node) );
/* 更新head指向第一个node */
head.head = node_pos;
FSEEK_HED_WRITE( fp, node_pos, (char *) &head, sizeof(head) );
CLOSE_FILE( fp );
}
/* 创建数据文件 */
if ( OPEN_FILE( DATA_FILE_NAME, "rb" ) == NULL )
{
fp = OPEN_FILE( DATA_FILE_NAME, "wb" );
CLOSE_FILE( fp );
}
}
static void insertData( char* con, uint key )
{
_data data;
/* 写入数据 */
data.len = strlen( con );
fp = OPEN_FILE( DATA_FILE_NAME, "ab" );
FSEEK_END_WRITE( fp, data.pos, con, data.len );
CLOSE_FILE( fp );
/* 写入索引 */
MALLOC_NODE( HeadBuf, FileHead );
Result res;
/* 读取索引头 */
OPEN_FILE_READ( INDEX_FILE_NAME, "rb+", HeadBuf, sizeof(FileHead) );
/* 查找树 */
SearchBTree( HeadBuf->head, key, &res );
printf( "offset=%u,len=%d\n", data.pos, data.len );
printf( "head=%u,node=%u\n", HeadBuf->head, HeadBuf->node );
printf( "key=%u,pt=%u,i=%hu\n", key, res.pt, res.i );
/* 插入树 */
InsertBTree( HeadBuf->head, key, res.pt, res.i, data );
FREE_NODE( HeadBuf );
CLOSE_FILE( fp );
}
static void PrintfBTree()
{
FileHead head;
BTNode node;
uint posArr[QUANEUE_LEN]; /* 队列长度 */
sint i = 0, j = 0, offset = 0, num = 0;
printf( "-------------------Head(0)-------------------------\n" );
OPEN_FILE_READ( INDEX_FILE_NAME, "rb", (char *) &head, sizeof(FileHead) );
printf( "FileHead_size:%ld----BTNode_size:%ld-----head_pos:%u----node_num:%u\n", sizeof(FileHead), sizeof(BTNode), head.head, head.node );
printf( "\n" );
memset( posArr, 0, sizeof(posArr) );
posArr[0] = head.head;
while ( posArr[num] )
{
printf( "-------------------Node(%d)-------------------------\n", num + 1 );
FSEEK_FIXED_READ( fp, posArr[num], (char *) &node, sizeof(BTNode) );
for ( i = 0; i <= node.keyNum; i++ )
{
printf( "index_ptr=%u, parent=%u, offset=%d, keyNum=%hu, key=%u, ptr=%u, data.len=%hu, data.pos=%u\n",
posArr[num], node.parent, i, node.keyNum, node.key[i], node.ptr[i], node.data[i].len, node.data[i].pos );
if ( node.ptr[i] )
posArr[++offset] = node.ptr[i];
}
printf( "\n" );
num++;
}
}
int main( int argc, char *argv[] )
{
if ( argv[1] && strcmp( argv[1], "show" ) == 0 )
{
PrintfBTree();
}else if ( argv[1] && strcmp( argv[1], "create" ) == 0 )
{
createInitFile();
}else if ( argv[1] && argv[2] && argv[3] && strcmp( argv[1], "id" ) == 0 )
{
insertData( argv[3], atoi( argv[2] ) );
}else{
printf( "hello world\n" );
}
return(0);
}
gcc编译环境： MacOs Catalina 10.15.2
索引数据记录在 ： index_btree 文件
文本数据记录在： data_file 文件
索引数据
结束
本次实现的只是最简单的B树的存储操作，并不包含删除更新等更详细的动作，因为只作为学习使用，所以不再去实现了，比如实现删除操作的话还要管理回收的文件Node块，相对流程会更复杂一些，当然以上只作为个人观点，仅供参考.
网友评论