个性化阅读
专注于IT技术分析

数据库快速索引原理!B树和B+树的实现原理和实例代码全解

点击下载

在上一节中,我们详细讨论了二叉树、AVL平衡二叉树、伸展树、B树和B+树,对树这种重要的数据结构进行了详细的讨论,如果你对数据结构和算法的基本概念还未了解,可以参考:数据结构、算法分析和算法设计。本节主要是对上一节内容的补充,因为上一节中对B树的实现并不好,上一节B树的插入过程如下图:

B树插入详细流程图解

这个算法逻辑实现上是有问题的,因为该算法在向下遍历的插入的时候还往回处理分裂,下面是上节B树的删除大体流程:

B树删除详细流程图

这个算法也是和插入一样类似的问题,在代码实现上会很复杂,大体是没大问题的,有兴趣的朋友可以指出来,下面重新介绍B树和B+树,相关的实现原理和代码实现,对于实现上会采取一种不同的更简单的方式,B+树是B树的扩展,B树可以说是一种广义树,B+树主要应用于大量数据索引的场景,例如操作系统的文件系统和数据库,如MySQL。

一、B树的数据结构和算法详解

1、B树的基本定义

在上一节我们是使用最大度数或阶数M来定义B树的,这种一般的定义方式如下:

  • 根结点度数M>=2;
  • 叶子结点的深度相同;
  • 非叶结点的度数:[M/2] <= T <= M,[]为向上取整符号;
  • 结点的关键字数:[M/2]-1 <= K <= M-1;
  • 关键字数K和结点度数T的关系为:K=T-1。

以上定义是正确的,但是问题是M如果为奇数在处理插入和删除的时候会有问题,这时候关键字数就为偶数,分裂结点就没那么方便了。

另一种B树的定义是使用最小度数t进行定义,该方式也是算法导论中采取的方式:

  • 最小度数t>=2,B树的最小度数与磁盘块的大小有关;
  • 根结点的关键字数最小为1;
  • 叶子结点的深度相同;
  • 非叶非根结点的度数:t <= T <= 2t;
  • 非根结点的关键字数:t-1 <= K <= 2t-1;

(6)关键数K和度数的关系为:K = T – 1。

之后你会发现使用最小度数实现B树会更加优雅,B树每个结点的关键字都按升序排列。设B树的关键字数为N,则B树的关键字数N >= 2t^h-1,h为B树的高度h <= log((N+1)/2),底数为t,t>=2,B树的所有一般操作的时间复杂度为O(log N),底数为t。

2、B树的数据结构

B树的结点至少包括:

  • 键值数组或关键字数组,长度为2t-1,长度为2t-1时结点为满;
  • 最小度数t,最大度数为2t;
  • 儿子指针数组,长度为2t;
  • 当前关键字数目n,最大值为2t-1;
  • 是否是叶子,用于标识一个结点是否是叶子结点,叶子结点没有儿子或其儿子为空。

下面是B树数据结构和算法声明的代码:

//
// Created by Once on 2019/7/22.
//

#ifndef TREE_BTREE_H
#define TREE_BTREE_H

// 键值数组结构
typedef struct column{
    int id; // 关键字
    char title[128];
} Column;

// B树结点
typedef struct bnode{
    int size; // 当前关键字数目
    Column **columns; // 键值数组
    struct bnode **children; // 儿子指针数组
    unsigned int leaf; // 是否为叶子
} BNode;

// B树ADT对外接口
typedef struct btree{
    unsigned int degree; // 最小度数
    BNode *root; // 根结点
    unsigned int size; // B树结点大小
} BTree;

// B树算法操作声明
extern BTree *btree_init(unsigned int degree);
extern int btree_is_full(BTree *btree);
extern int btree_is_empty(BTree *btree);
extern int btree_add(BTree *btree, Column *column);
extern int btree_delete_by_id(BTree *btree, int id);
extern Column *btree_get_by_id(BTree *btree, int id);
extern void btree_traverse(BTree *btree, void(*traverse)(Column*));
extern int btree_clear(BTree *btree);

#endif //TREE_BTREE_H

3、创建B树

C语言使用malloc创建一个B树,可预先创建一个根结点,也可以在插入数据的时候创建,初始化数据结构中的基本值,包括当前关键字数,是否是叶子,在处理B树持久化的时候,需要将新的根结点写入硬盘。这里仅仅初始化B树,不预先创建根结点:

BTree *btree_init(unsigned int degree){
    BTree *btree = (BTree*)malloc(sizeof(BTree));
    if(!btree){
        perror("init b tree error.");
        return NULL;
    }
    btree->root = NULL;
    btree->size = 0;
    btree->degree = degree;
    return btree;
}

4、B树遍历算法

树的遍历原则是以一个关键字为中心,左右儿子为该关键字的上限和下限,在B树遍历中,需要遍历结点上的关键字,在这里可使用while或for循环顺序遍历,时间为O(t),也可以使用二分法遍历,时间为O(log t),顺序遍历一个B树的描述如下,这是一个中序遍历:

  • 使用for循环,上限为当前结点关键字数size,索引为i;
  • 先遍历第i个非叶子儿子,此时即递归自身;
  • 处理第i个关键字;
  • 后处理第i+1个儿子,递归自身;
  • 处理第i+1个关键字;
  • 以上操作循环处理,跳出循环后需要处理最后一个儿子。

B树遍历算法代码如下:

static void traverse_tree(BNode *root, void(*traverse)(Column*)){
    int i;
    for (i = 0; i < root->size; ++i) {
        if(!root->leaf)
            traverse_tree(root->children[i], traverse);
        traverse(root->columns[i]);
    }
    if(!root->leaf)
        traverse_tree(root->children[i], traverse);
}

void btree_traverse(BTree *btree, void(*traverse)(Column*)){
    if(btree == NULL || btree->size == 0)
        return;
    traverse_tree(btree->root, traverse);
}

5、B树搜索算法

B树的搜索算法输入参数为B树的根结点root和待查找的关键字k,输出为NULL,找到对应的关键字则返回目标结点以及目标关键字的索引位置,这里实现仅仅返回关键字对应的值。

B树搜索的重点在于确定关键字的位置,包括确定相等关键字的位置,同时确定下层儿子的位置,这里要说一下关键字的索引和儿子的索引的关系,如下图:

B树索引和儿子结点索引的关系

结点上确定关键字位置的算法有两种,线性搜索和二分法搜索,线性搜索的时间为O(t),此时B树的总时间为O(t log N),底数为t,二分法搜索的时间为O(log t),此时B树的总时间为O(log t log N)),B树搜索算法代码如下:

// 顺序查找结点关键字,每个结点最多关键字为2t-1,时间复杂度为O(2t-1),即O(t)
static int seq_search(const Column *array[], const int len, const int value){
    int i = 0;
    while(i <= len - 1 && value > array[i]->id)
        i++;
    return i;
}

// 二分法查找结点上相同的关键字、确定儿子访问位置,每个结点关键字数为2t-1,时间复杂度为O(log(2t-1)),即O(log t)
static int binary_search(Column *array[], const int len, const int value){
    int start = 0, end = len - 1, index = 0, center = (start + end) / 2;
    while(start <= end){
        if(value == array[center]->id){
            index = center;
            break;
        }
        else if(value > array[center]->id){
            index = center + 1;
            center += 1;
            start = center;
        }
        else{
            index = center;
            center -= 1;
            end = center;
        }
        center = (start + end) / 2;
    }
    return index;
}

static Column *btree_get(BNode *root, int id){
    int index = binary_search(root->columns, root->size, id);
    if(index < root->size &&  root->columns[index]->id == id)
        return root->columns[index];
    else if(root->leaf)
        return NULL;
    else
        return btree_get(root->children[index], id);
}

Column *btree_get_by_id(BTree *btree, int id){
    if(btree == NULL || btree->size == 0)
        return NULL;
    return btree_get(btree->root, id);
}

6、B树插入算法

B树的插入最主要就是结点分裂了,一般来说如果一个结点满了,则分裂成两个结点,中间的关键字插入到父结点,这样向上分裂,但是关键字是插入到叶子结点的,等到插入关键字再分裂结点,则处理会比较麻烦。

这里B树插入采用另一种方式:插入关键字从根结点自上而下查找关键字所属位置,将关键字添加到叶子结点上;沿途经过的结点若满(满的关键字数为2t-1)则分裂结点,以第(t-1)个关键字为分界点,分成两个结点,每个结点的关键字数为t-1,将第t-1个关键字插入到父结点,这样将关键字插入到叶子结点时就不需要再分裂,如下图,插入6之前先将根结点分裂,然后再从根结点上获取新的路径插入到叶子结点上。

B树插入示例图解

B树插入算法的大体流程如下图所示,其总体流程包括满结点分裂、非满结点插入:

取出根结点,如果根结点已满则分裂该结点,然后更新根结点,向下选择路径,检查途径的结点,如果是内部结点,检查该结点的儿子结点是否已满,若满则分裂,否则继续向下,如果是叶结点则插入关键字,插入结束。

B树插入算法详细流程图

(1)分裂结点算法

分裂结点分裂的不是当前结点,而是当前结点的儿子结点,分裂结点算法的输入参数包含儿子为满的父结点,以及满儿子在父结点中的索引位置i,这个i在向下选择路径的时候可以求得到。

在自上而下查找关键字位置时,分裂途径的满结点,关键字数为2t-1为满,分裂的结点包括叶子结点,这样在分裂当前结点时,可保证它的父结点不是满的,也就是不需要再向上分裂了,分裂算法的详细描述如下:

  • 以当前结点作为父结点,检查向下的儿子s结点是否已满,而根结点的分裂会导致创建新的根结点n;
  • 如果根结点已满,则创建并初始化新结点n(包括当前关键字数、是否为叶结点),在节点s中将从第t个开始的关键字转移到n中,非叶结点需要从第t个开始转移儿子到n中;
  • 将新结点添加到当前结点(父结点)作为儿子;
  • 将第t-1个关键字添加到当前结点(父结点)中。

以上分裂算法都是针对当前结点分裂儿子结点,在路径每一个结点上都需要检查,若结点已满则调用该分裂算法,代码如下:

/**
 * 1、创建新结点n
 * 2、转移关键字到n
 * 3、转移儿子到n
 * 4、n添加作为parent的儿子
 * 5、将中间关键字添加到parent
 * */
static int split_child(BTree *btree, BNode *parent, int index){
    BNode *left = parent->children[index];
    BNode *right = (BNode*)malloc(sizeof(BNode));
    if(!right)
        return 0;
    right->columns = (Column**)malloc(sizeof(Column*) * (2 * btree->degree - 1));
    right->children = (BNode**)malloc(sizeof(BNode*) * (2 * btree->degree));
    if(!right->columns || !right->children)
        return 0;
    right->leaf = left->leaf;
    for (int i = btree->degree; i < left->size; ++i) {
        right->columns[i - btree->degree] = left->columns[i];
    }
    if(!left->leaf){
        for (int i = btree->degree; i < left->size + 1; ++i) {
            right->children[i - btree->degree] = left->children[i];
        }
    }
    right->size = btree->degree - 1;
    left->size = btree->degree - 1;
    for (int k = parent->size; k > index; --k) {
        parent->columns[k] = parent->columns[k - 1];
    }
    parent->columns[index] = left->columns[btree->degree - 1];
    for (int j = parent->size + 1; j > index + 1; --j) {
        parent->children[j] = parent->children[j - 1];
    }
    parent->children[index + 1] = right;
    parent->size++;
    return 1;
}

(2)B树插入关键字

完整的插入算法输入参数包括根结点和待插入的关键字,以上的分裂算法只处理满结点的情况,那么非满结点也需要做处理,下面是该算法的完整描述:

  • 先检查B树的根结点,如果根结点为满,则创建一个新的根结点,调用分裂算法进行分裂,处理完成后再以新的根结点为起点调用非满插入算法;
  • 关键字数小于2t-1为非满,如果当前结点为叶子结点,则将关键字插入到结点中;
  • 如果当前结点为内部结点,获取下一个儿子结点,检查是否需要分裂,分裂完成后,再递归调用非满插入算法。

同样的,以上检查结点是否已满,除了根结点外,都是检查儿子结点的,下面是完整的关键字插入代码:

static int add_none_full(BTree *btree, BNode *root, Column *column){
    int index = binary_search(root->columns, root->size, column->id);
    if(root->leaf){
        if(index < root->size && root->columns[index]->id == column->id){
            strcpy(root->columns[index]->title, column->title);
            return 1;
        }
        Column *c = (Column*)malloc(sizeof(Column));
        if(!c)
            return 0;
        c->id = column->id;
        strcpy(c->title, column->title);
        for (int i = root->size; i > index; --i) {
            root->columns[i] = root->columns[i - 1];
        }
        root->columns[index] = c;
        root->size++;
        return 1;
    }
    else{
        if(root->children[index]->size == 2*btree->degree - 1){
            if(split_child(btree, root, index)){
                if(column->id > root->columns[index]->id)
                    index++;
            }
            else
                return 0;
        }
        return add_none_full(btree, root->children[index], column);
    }
}

static int add_node(BTree *btree, BNode *root, Column *column){
    if(!root){
        root = new_node(btree);
        if(!root)
            return 0;
        Column *c = (Column*)malloc(sizeof(Column));
        if(!c)
            return 0;
        c->id = column->id;
        strcpy(c->title, column->title);
        root->leaf = 1;
        root->columns[0] = c;
        root->size = 1;
        btree->root = root;
        btree->size++;
        return 1;
    }
    else{
        if(root->size == 2*btree->degree - 1){
            BNode *node = new_node(btree);
            if(!node)
                return 0;
            node->leaf = 0;
            node->size = 0;
            btree->root = node;
            node->children[0] = root;
            btree->size++;
            if(split_child(btree, node, 0)){
                int i = 0;
                if(node->columns[0]->id < column->id)
                    i++;
                return add_none_full(btree, node->children[i], column);
            }
            return 0;
        }
        else
            return add_none_full(btree, root, column);
    }
}

int btree_add(BTree *btree, Column *column){
    if(btree == NULL || column == NULL)
        return 0;
    return add_node(btree, btree->root, column);
}

7、B树删除算法

B树的删除操作比较复杂,下面我们来一步步分析,我们可以想到,删除的情况有两种:内部结点和叶子结点,这里删除的方式也是和插入类似,一次遍历完成删除操作,因为删除一个关键字可能会导致结点关键字不足t-1个,这就需要借或者合并相邻结点。

这里我们采取这样的方式,一般来说非根结点关键字数至少为t-1个(根结点至少为1个关键字),递归下降遍历,对每个沿途经过的结点,保证结点的关键字说为t(比最小关键字数t-1多1),儿子结点关键字不足t时,从父结点下移一个到儿子中,将兄弟结点的关键字上移一个到父结点,当前结点关键字为空,删除当前结点,让儿子成为新的根,这种方式保证内部结点的关键字数至少为t,这样从内部结点删除一个关键字时就不会导致该结点为空或少于t-1个关键字,下图是B树删除操作的大体流程,下面我们详细讨论操作流程:

B树删除算法详细流程

删除操作输入参数为根结点和待删除的关键字k,删除的操作分为以下三种情况:

  • k在叶结点中:直接删除关键字k,如果不存在也删除结束;
  • k在内部结点中:以当前待删除的关键字k为中心,k有左右儿子:
  • k的左儿子关键字数>=t,将左子树的最大值M替换k,递归向下删除M;
  • k的右儿子关键字数>=t(k的左儿子的关键字数<t),将右子树的最小值m替换k,递归向下删除m;
  • k的左右儿子关键字数==t-1,将k和左右儿子合并进左儿子,在当前结点中释放右儿子和k,从左儿子递归向下删除k。
  • k不在当前结点中:当前结点的向下儿子s,k有可能在以s为根的结点中,此时我们需要将s的关键字调整至少t个关键字,(向左借、向右借、合并左或右)调整的情况如下:
  • s结点只有t-1个关键字(相邻兄弟关键字>=t),将当前结点的一个关键字下移到s中,将左或右兄弟一个关键字上移到当前结点,将兄弟中关键字相应的儿子移到s结点中;
  • s结点和所有相邻兄弟结点都只有t-1个关键字,将s和其中一个兄弟合并,将当前结点的一个关键字移到新合并的结点中。

删除算法可分为:当前结点存在关键字,则删除叶子结点或者内部结点的关键字,不存在则需要检查儿子结点进行填满t个关键字的操作。B树的完整源码可在github上查看:https://github.com/onnple/B-TREE-C,该项目的删除操作有bug,但是由于时间问题就不再进行调试了,感兴趣的朋友可以指正一下。

二、B+树

B+是B树的扩展,它和B树在结构上主要的不同在于,B+树的所有叶结点是使用链表链接的,而且B+树的叶结点包含了全部的关键字,下面B+树图片取自于维基百科:

B+树实例图解

B+树的主要应用在操作系统的文件系统和数据库,这里就不实现B+树了,需要应用B+树的特性那么使用例如MySQL等数据库是最好的方式。

如果需要自定义实现B+树,B+树的数据结构和B树的基本一样,不过叶子结点需要增加左右兄弟的指针。B+树的算法操作也和B树基本一样,但是要注意因为B+树的所有叶子结点包含了所有的关键字,所以在插入操作分裂结点中,中间的关键字除了插入父结点,需要保留在叶子上,删除操作则需要把叶子上相同的关键字一并删除。

三、MySQL数据库索引引擎实现原理

如果你用过MySQL数据库的话,可能知道在MySQL存储数据有几种文件,例如.frm文件、.myi文件、.myd文件和.ibd文件,首先.frm文件是MySQL用于表示表结构的文件,一般创建一个新表都会创建这样的文件。

MySQL数据库有两大索引引擎:MyISAM引擎和InnoDB引擎,这两个索引引擎都是基于B+树实现的,对于MyISAM索引引擎,它是一个非聚簇索引,即在叶子结点上存储数据的地址,所以使用MyISAM索引存储的数据分为两个文件:.myi文件和.myd文件,这两个文件分别存储索引和真实数据。

而对于InnoDB引擎,它直接在叶结点存储数据本身,因此是聚簇索引,只使用一个文件存储索引和真实数据,该文件就是.ibd文件。

1、MySQL索引引擎实现原理

首先我们要清楚,实现MySQL索引引擎并不是直接存储一个B+树,甚至并不需要一个真正的B+树,实际存储的是一个结点的数据,一次IO读取一个结点,从这个结点找出下一个结点的位置再次调用IO读取,所以索引引擎是一个逻辑上的B+树。

为什么要使用B+树索引数据?主要还是因为速度的问题,我们的真实数据存储在磁盘上,一般在内存里面的操作都不算耗时,反而机械磁盘耗时会比较明显,因为磁盘读取有真实的机械性操作,影响磁盘读取速度的主要因素是:盘片的旋转和磁臂的移动。那么如何实现速度最大化呢?那就是B+树了,B+树读取海量的数据只需要O(log N)次操作,而且其底数t可以最大化,InnoDB是将根结点常驻内存,以一个结点为一个数据单位,一次IO读取一个结点,MySQL设置的一个数据页为16K。

为什么使用B+树而不是B树?要知道B+树的结点不存储任何真实数据,只存储索引数据,而B树是两者都存储,这样相同大小16K的一个结点,B+树存储的索引数据比B树的多很多,这意味着B树的IO操作次数会比B+树的多,所以使用B+树实现索引更有优势,另外一个原因是因为B+树的所有叶结点都是相连的,B+树可以很方便地进行顺序访问或范围性访问。

MySQL在索引引擎实现上并不是严格遵守B+树的定义,例如结点分裂,MySQL采取的原则是空间优先,只要结点空间足够就插入,尽量最大化利用空间。

2、InnoDB存储引擎索引原理

(1)存储结构

A、表空间(table space):一个存储文件的主题,由段组成;

B、段(segment):由簇组成,可分为数据段、索引段和回滚段;

C、区/簇(extent):由64个连续的页空间组成(64x16k),段的最小单位,它是一个连续分配的段空间;

D、页(page):磁盘块的最小单元,16k大小,常见的页有数据页(B-tree Node page)、事务数据页(Transacation system page)、Undo页和系统页,又称为一个记录(page==record),一个页等于一个结点。

(2)数据存储原理

磁盘由盘面、磁头、磁道(Track)、柱面(Cylinder)和扇区(Sector)组成,盘面从上而下从0开始编号,磁头由上而下从0开始编号,磁道由外向内从0开始编号,磁道的一段圆弧叫做扇区,扇区从1开始编号,柱面编号和磁头是一样的。

磁盘的数据寻址有两种方式:逻辑地址和磁盘地址,逻辑地址则是编程代码中获取的数据地址,一般用十六进制表示,磁盘地址是数据的物理地址,一般使用一个三位码表示(柱面号,磁头号,扇区号)。

磁盘IO读写的速度影响因素包括磁盘存储介质和机械运动,上面对索引引擎的存储结构的设计,一个依据是计算机局部性原理,也就是说设计结点的大小需要考虑磁盘块的大小,计算机局部原理是说,当一个数据被使用到时,附近的数据也会被马上用到,程序运行所需数据通常比较集中,在附近柱面,或附近磁头,或附近的扇区,另外程序预读数据也可以提高IO效率,预读的数据长度为页的整数倍。

赞(0)
未经允许不得转载:srcmini » 数据库快速索引原理!B树和B+树的实现原理和实例代码全解

评论 抢沙发

评论前必须登录!