B+树索引实验报告VIP专享

实验一 B+树索引 一、 实验内容： 1 . B+树索引的初使建立； 2 . B+树索引的维护（插入删除）； 3 . B+树索引的查找； 二、 实验要求： 1 . 外存索引； 2 . 数据地址可以用逻辑地址模拟； 3 . 能以图形化方式展示索引结构； 三、 实验步骤： 本实验代码实现使用的的是 C 语言。 1 . 索引文件结构的表示： 由于直接读写管理磁盘块涉及很多底层的操作，所以我们是用一个文件来表示一个硬盘，然后模拟这些操作。 我们的思路是在这个硬盘的第 1 块里存放这个文件的头部信息（比如现在哪个块是可以用的，哪个块已经被用了，等等），剩下的其它块用来存放记录索引等等。 具体的定义在”disk.h”里面，我们首先定义了一个块的大小 BLOCK_SIZE，在本实验里面我们定义为 4K，然后我们实现了一些具体的操作：得到下一个空块，设置一个块的状态（可用，不可用），读写一个索引块，读写索引文件头信息。 具体实现： next_empty_block(… )：得到下一个可用的空块。我们是用位图来管理空块，在索引 文件头里面定义了一个bitmap[]；然后用某一位是0（表示该块为空块）还是1 来表示所对应的块是不是空的。所以该函数就是从头扫描一个为0 的位，然后把块号返回以提供下一个索引块存放的位置。 set_status_block(… )：设置某块的状态。将该所代表的位置为0 或 1。 read_btidx_block(… )：读某索引块。先把文件指针定位到要读的块的位置（块从 0 开始编号，块i 在文件中的偏移就是BLOCK_SIZE * i），然后读出该索引块的内容。 write_btidx_block(… )：写某索引块。以下同上。 read_bthdr_block(… )：读索引文件头。 write_bthdr_block(… )：写回索引文件头。 2. B +树节点结构及相关操作定义： 1 ) 首先定义B+树每个节点所能存的最大 KEY 值数 KEY_NUM，我们定义为256。 2 ) 然后定义B+树的节点结构 btree_node： /* b+ tree node struct */ struct btree_node { int d; /* key num of a node */ key_t key[KEY_NUM]; /* n search keys */ int ptr[KEY_NUM + 1]; /* n+1 pointes */ }; d 表示该节点当前所存放的KEY 的数目，key[KEY_NUM]是存放 KEY 值的数组，ptr[KEY_NUM + 1]是存放指针（数据地址）的数组，这个数据地址通过逻辑地址模拟：当结点为内部结点时，记录的是指向该键值的下一个子块号；当结点为叶子结点时，记录的是数据(元...