1 红黑树处理海量数据时的存在问题

海量数据的索引本身也很大，无法全部读入到内存中处理，必须反复从磁盘中读数据，而采用红黑树时的数据寻址次数多(高度logn)，这将引起大量的磁盘IO操作，导致查询时间长，性能差。

解决思路： 采用多叉树降低树的高度。

2 B树

一个5阶B树示例（图片为转载，www.0voice.com）

对于一个1024叉的B树，最快两次寻址就可以检索4G的数据单元（每个单元4K）。（4G=10210244K）

2.1 B树的性质

一颗M阶B树T，满足以下条件

1. 每个结点至多拥有M棵子树（M为人为设置的限制，M棵子树对应M-1个key），或者叫M个子节点
2. 根结点至少拥有两棵子树（否则左右高度将不同）
3. 除了根结点以外，其余每个分支结点至少拥有M/2棵子树（确保了左右子树的平衡）
4. 所有的叶结点都在同一层上（高度相同）
5. 有k棵子树的分支结点则存在k-1个关键字（两个节点夹一个关键字key），关键字按照递增顺序进行排序
6. 关键字数量满足ceil(M/2)-1 <= n <= M-1（结合1、3和5得来，3决定其下限，1和5决定其上限）

M建议为一个偶数，则key的最大数目为M-1是一个奇数，当节点的key达到最大而开始分裂时，正好可以从索引为M/2-1的中间位置开始分裂。

为了方便后续描述，我们设关键字数量下限kmin=ceil(M/2)-1，上限kmax=M-1

2.2 B树结构体定义

typedef int KEY_TYPE;
typedef struct btree_node BTREE_NODE;
struct btree_node
{KEY_TYPE* keys;BTREE_NODE** children;int keyNum;        // 当前节点key的数量int isLeaf;
} ;typedef struct btree
{BTREE_NODE* root;int kMaxNum;        // 节点的最大key数量int kMinNum;        // 除根节点外，每个节点的最小key数量int kMidIdx;        // 节点中间可以用于分裂的那个key索引int order;          // 阶数
} BTREE;

2.3 B树的添加操作

对于B树，所有的数据插入都是插到叶子节点上，这点与BST及红黑树是类似的。

2.3.1 节点子树未满(num < M-1)

以一个6阶B树为例，直接按顺序插入即可。

若节点子树已满，则需要按后面这样分为根节点和叶节点进行处理。

2.3.2 根节点分裂

当根节点的子节点数量达到上限M（或者说key的数量达到上限kmax）时，不能继续插入新的key，必须进行分裂后再插入。

分裂根节点的方法为：新建一个节点并且将新节点的第一个子节点指向原来的根节点，然后以新节点作为父节点进行分裂。

2.3.3 叶节点分裂

• 父节点未满
  当叶节点的子节点数量达到上限M（或者说key的数量达到上限kmax）时，不能继续插入新的key，必须进行分裂后再插入。其中，分裂出来的中间key必须合入其父节点，步骤为：1）将节点中间的K先移到父节点最后；2）新建一个节点保存后面的L、M；3）将K右边的子节点指针指向新节点；4）在新节点中插入N。
  
• 父节点也满了
  此时，不能直接将分裂出来的中间位置key合入父节点，必须再往上处理。
  
  如果向上分裂达到了根节点，则按根节点分裂的方法处理。

实际上这里如果用代码实现就是一个向下递归的处理过程，处理下一级子节点前，先判断一下这个子节点是否为满，如果满了，先将其分裂再向下继续处理

也可以参考这篇文章的方法自底向上处理：B树和B+树的插入、删除图文详解

2.3.4 B树添加节点的代码实现

static BTREE_NODE* _create_node(BTREE* t, int isLeaf)
{BTREE_NODE* node = (BTREE_NODE*)malloc(sizeof(BTREE_NODE));if(node == NULL)assert(0);node->keys = (KEY_TYPE*)calloc(t->kMaxNum, sizeof(KEY_TYPE));node->children = (BTREE_NODE**)calloc(t->order, sizeof(BTREE_NODE*));if(node->keys == NULL || node->children == NULL)assert(0);memset(node->keys, 0, t->kMaxNum * sizeof(KEY_TYPE));memset(node->children, 0, t->order * sizeof(BTREE_NODE*));node->keyNum = 0;node->isLeaf = isLeaf;return node;
}// parent 节点的下标为n的孩子进行分裂
static void _split_child(BTREE* t, BTREE_NODE* parent, int n)
{int i, j;if(n < 0 || n > t->kMaxNum) assert(0);BTREE_NODE* splitChild = parent->children[n];BTREE_NODE* newSibling = _create_node(t, splitChild->isLeaf);i = parent->keyNum - 1;// 先将父节点中处于分裂节点之后的key都往后移以腾出空间while(i >= n){parent->keys[i + 1] = parent->keys[i];parent->children[i + 2] = parent->children[i + 1];i--;}   // 此时插入key的位置为i+1, 插入的key左右两边的子节点为i+1和i+2，i+1节点不变，i+2指向新节点parent->keys[i + 1] = splitChild->keys[t->kMidIdx]; // 分裂节点的中间位置的key上移到父节点parent->children[i + 2] = newSibling;// 将分裂节点后半部分拷贝到新节点中for(i = t->kMidIdx + 1, j = 0; i < t->kMaxNum; i++, j++){newSibling->keys[j] = splitChild->keys[i];newSibling->children[j] = splitChild->children[i];}newSibling->children[j] = splitChild->children[i]; // 最后一个关键字右侧的子节点别忘了拷贝splitChild->keyNum = t->kMinNum;newSibling->keyNum = t->kMinNum;parent->keyNum++;
}// 若当前节点未满，则使用_insert_notfull进行插入操作，否则先分裂后再向其子节点进行插入操作
static void _insert_notfull(BTREE* t, BTREE_NODE* node, KEY_TYPE key)
{int i;// 一直往下递归找到叶子节点if(node->isLeaf){i = node->keyNum - 1;while( i >= 0 && key < node->keys[i]){node->keys[i + 1] = node->keys[i];  // 找插入位置的过程中先把较大的关键字后移以腾出空间i--;}node->keys[i + 1] = key;node->keyNum++; // 关键字数量加1}else{// 找到对应的子树i = node->keyNum - 1;while( i >= 0 && key < node->keys[i]) i--;if(node->children[i + 1]->keyNum == t->kMaxNum) // 判断子树是不是满的，如果是满的，要先将子树分裂{_split_child(t, node, i + 1);i++; // 因为子节点分裂后有一个key上升到待插入节点的后面，因此索引要加1}// 递归进入子树if(key > node->keys[i]) // 大于当前key，插到其右边(i + 2)_insert_notfull(t, node->children[i + 1], key);else                            // 大于当前key，插到其右边(i + 1)_insert_notfull(t, node->children[i], key);}
}void btree_insert(BTREE* t, KEY_TYPE key)
{BTREE_NODE* root = t->root;if(root->keyNum == t->kMaxNum)  // 若根节点已满则先做单独处理{// 创建一个新节点作为root，然后以该节点为父节点进行分裂操作root = _create_node(t, 0);root->children[0] = t->root;    // 新节点的第一个子节点指向原来的根节点t->root = root;_split_child(t, root, 0);// 根节点分裂完成，继续向下找到可以插入的未满叶节点if(key < root->keys[0])_insert_notfull(t, root->children[0], key);else_insert_notfull(t, root->children[1], key);}else{_insert_notfull(t, root, key);}
}

2.4 B树的删除操作

首先递归遍历找到key所在的子树。若待删数据的key位于中间节点（非叶子节点），则可以用其后继节点的数据进行覆盖，然后转而去删除后继节点的数据。这与二叉搜索树以及红黑树的删除逻辑一致。因此，只需要考虑删除叶节点数据的情况。

2.4.1 直接删除

待删叶节点的关键字数量大于下限kmin，则直接删除这个关键字数据即可。

2.4.2 借位

对于本身关键字数量已经等于下限kmin的情况：若左、右兄弟节点有任一个的关键字数量大于下限kmin，则可以向其借位。其中，向左边的子树借最高位，向右边的子树借最低位。一般先看左子树再看右子树。

1. 向左边兄弟子树借位
   

2. 向右边兄弟子树借位
   

由于B树的节点一般没有保存父节点，在删除过程中，当前节点已经进入其子节点后，就难再返回去操作父节点了。一种比较简便的方法是：向下查询待删节点时，进入子节点前先判断一下子节点的key数量是否到达下限，如果是，则立即进行借位操作，扩充子节点的元素大小，之后再进行进入子节点进行删除操作时就不必再关心父节点了。

2.4.3 合并

如果左右兄弟都不够借位，则需要将父节点的一个key下移并与左右两个子树合并，完成之后再删除对应节点。

不难发现，要是被借位的父节点也只有kmin个子树，显然不能直接借。为了方便处理这种情况，依然地，在向下查找key值的过程中，除了根节点外，遇到节点的子树数量等于kmin时，就先进行合并操作，这样后面就可以避免父节点不够借位的情况出现。

2.4.4 B树删除节点的代码实现

static void _destroy_node(BTREE_NODE* parent)
{if(parent){if(parent->keys)free(parent->keys);if(parent->children)free(parent->children);free(parent);}
}// 将parent节点的索引为n的元素下放并与其左右子节点合并
static BTREE_NODE* _merge_children(BTREE* t, BTREE_NODE* parent, int n)
{int i, j;BTREE_NODE* leftChild = parent->children[n];BTREE_NODE* rightChild = parent->children[n + 1];leftChild->keys[leftChild->keyNum] = parent->keys[n];for(i = leftChild->keyNum + 1, j =0; j < rightChild->keyNum; i++, j++){leftChild->keys[i] = rightChild->keys[j];leftChild->children[i] = rightChild->children[j];   // 右节点的子节点转移到左节点后面}leftChild->children[i] = rightChild->children[j];   // 右边最后一个子节点leftChild->keyNum += 1 + rightChild->keyNum;        // 节点数增加，1为父节点合入_destroy_node(rightChild);  // 将右子节点释放掉for(i = n; i < parent->keyNum - 1; i++){parent->keys[i] = parent->keys[i + 1];parent->children[i + 1] = parent->children[i + 2];}parent->children[i + 1] = NULL;parent->keyNum--;// !! 如果是根节点的最后一个元素被合并入子节点，根节点将为空// 此时需要释放原来的根节点，将新的子节点作为根节点if(parent->keyNum == 0){t->root = leftChild;_destroy_node(parent);}return NULL;
}static void _delete_key(BTREE* t, BTREE_NODE* node, KEY_TYPE key)
{int i;BTREE_NODE* child;BTREE_NODE* leftSibling;BTREE_NODE* rightSibling;int targetIdx = 0;  // targetIdx要么是当前节点中待删key的索引if (node == NULL || node->keyNum == 0)return ;// 从节点的元素中从前往后找到第一个大于key的元素while(targetIdx < node->keyNum && node->keys[targetIdx] < key) targetIdx++;// 1 - 找了到匹配的keyif(targetIdx < node->keyNum && key == node->keys[targetIdx]){// 1.1 - 看当前节点是否是叶子节点if(node->isLeaf)    // 是叶子节点，执行删除操作{for(i = targetIdx; i < node->keyNum - 1; i++)node->keys[i] = node->keys[i + 1];node->keyNum--;// 此处理论上不需要判断节点中的key是否都被删完了，// 因为这种情况只有root节点会出现，而我们可以选择不将root节点释放// 为什么删除叶节点的元素时不需要判断key的数量是否少于下限kmin？// 因为下面的分支2在向下查找的过程中会保证子节点的元素数量一定大于kmin}else    // 1.2 - 不是叶子节点，而是中间节点，则寻找后继节点的key来替换{// 在该key左右两边的子节点中选一个后继节点if(node->children[targetIdx + 1]->keyNum >= t->kMinNum){   // 1.2.1 - 优先选右边，即子节点的索引为 targetIdx + 1，但要求子节点的元素数量大于下限kminnode->keys[targetIdx] = node->children[targetIdx + 1]->keys[0]; // 后继节点的元素替换_delete_key(t, node->children[targetIdx + 1], node->children[targetIdx + 1]->keys[0]); // 转而去后继节点种删除}else if(node->children[targetIdx]->keyNum >= t->kMinNum){   // 1.2.2 - 右边不行就选左边，即子节点的索引为 targetIdx，同样要求子节点的元素数量大于下限kminnode->keys[targetIdx] = node->children[targetIdx]->keys[0]; // 后继节点的元素替换_delete_key(t, node->children[targetIdx], node->children[targetIdx]->keys[node->keyNum - 1]); // 转而去后继节点中删除}else{   // 1.2.3 - 左右子节点都不行，那就与他们合并吧_merge_children(t, node, targetIdx);_delete_key(t, node->children[targetIdx], key); // 继续到合并的节点中去删除}}}else    // 2 - 当前节点中没有待删的key，需要到子节点中去找{// 显然要查找的下一个子节点索引为targetIdxchild = node->children[targetIdx];if(child == NULL){   // 都找到叶子节点的了还没找到，child就是NULL了printf("there is no such key in tree!\n");return ;}// 进入字节点查找前，先确保子节点的key数量大于kminif(child->keyNum <= t->kMinNum)  // 2.1 - 子节点不满足要求，需要扩充子节点{   // 只能去左右兄弟节点那里拉壮丁leftSibling = NULL;     // 左右兄弟节点的指针初始化为NULL，以便判断是否存在rightSibling = NULL;if (targetIdx - 1 >= 0)leftSibling = node->children[targetIdx - 1];if (targetIdx + 1 <= node->keyNum) rightSibling = node->children[targetIdx + 1];if(rightSibling && rightSibling->keyNum > t->kMinNum){   // 2.1.1 - 向右兄弟借位，对应的子节点索引是targetIdx+1。前提是右兄弟要存在哈child->keys[child->keyNum] = node->keys[targetIdx];child->children[child->keyNum + 1] = rightSibling->children[0];node->keys[targetIdx] = rightSibling->keys[0];for(i = 0; i < rightSibling->keyNum - 1; i++){rightSibling->keys[i] = rightSibling->keys[i + 1];rightSibling->children[i] = rightSibling->children[i + 1];}rightSibling->children[i] = rightSibling->children[i + 1];  // 最后右边的一个子节点别忘了rightSibling->children[i + 1] = NULL;child->keyNum++;rightSibling->keyNum--;}else if(leftSibling && leftSibling->keyNum > t->kMinNum){   // 2.1.2 - 向左兄弟借位，前提也是左兄弟要存在for(i = child->keyNum; i > 0; i--){child->keys[i] = child->keys[i - 1];child->children[i + 1] = child->children[i];}child->children[i + 1] = child->children[i];  // 最后左边的一个子节点别忘了child->keys[0] = node->keys[targetIdx - 1];child->children[0] = leftSibling->children[leftSibling->keyNum];leftSibling->children[leftSibling->keyNum] = NULL;node->keys[targetIdx - 1] = leftSibling->keys[leftSibling->keyNum - 1];child->keyNum++;leftSibling->keyNum--;}else{   // 2.1.3 - 左右兄弟都不行，还是合并他们吧if(rightSibling)_merge_children(t, node, targetIdx);    // 将右节点合并进来else if(leftSibling){_merge_children(t, node, targetIdx - 1);child = leftSibling;    // 与左节点合并时，是合入左节点，因此子节点指针要转移}elseassert(0); // 这种情况不可能出现}}_delete_key(t, child, key); // 进入到子节点继续查找待删的key}
}int btree_delete(BTREE* t, KEY_TYPE key)
{if(t == NULL)return -1;_delete_key(t, t->root, key);return 0;
}

2.5 B树初始化和遍历

1）初始化代码

int btree_init_tree(BTREE* t, int order)
{if(order < 2 || t == NULL)return -1;t->order = (order & 1) + order;   // 确保阶数为偶数t->kMidIdx = (t->order >> 1) - 1; // 当一个节点已满需要分裂时，kMidIdx是位于中间那个key的索引t->kMinNum = t->kMidIdx;          // 除根节点外的节点元素下限kmint->kMaxNum = order - 1;           // 最大元素t->root = _create_node(t, 1);return 0;
}

2）遍历代码

该遍历代码中的_traversal()函数可以比较直观地在控制台输出B树的结构。

static void _traversal(BTREE_NODE* node, int lvl)
{int i;if(node == NULL){return ;}for(i = 0; i < lvl; i++)printf("\t\t\t\t");printf("level=%02d keyNum=%02d isLeaf=%c\n", lvl + 1, node->keyNum, node->isLeaf?'Y':'N');for(i = 0; i < lvl; i++)printf("\t\t\t\t");for(i = 0; i < node->keyNum; i++)printf("%c ", node->keys[i]);printf("\n");for(i = 0; i <= node->keyNum; i++){_traversal(node->children[i], lvl + 1);}}void btree_traversal(BTREE* t)
{_traversal(t->root, 0);
}

2.5 案例分析

设计一个图片存储索引组件

1. 图片的数量是巨大的。
2. 可以添加图片，可以删除图片（以首字母作为key）
3. 可以通过图片名称进行查找
4. 添加，删除，查找都是对单一图片进行操作

3 B+树

B+树是B树的变体。B树从某种程度上来说是个学术产品，相比之下B+树的实用性更强，在实际中应用更多。但B+树的代码实现也比B树更加复杂。

3.1 B+树性质

• 存在两种类型的节点：内部结点（也称索引结点）和叶子结点。根结点可以是内部结点或叶子结点，且关键字个数最少可以为1个。
• 内部结点只用于索引，不保存数据；所有数据都保存在叶子结点中。
• 一个M阶B+树，内部节点最多有M-1个关键字key，叶子节点最多有M-1个关键字和数据。
• 节点内key和子节点指针的排列方式与B树一致。
• 每个叶子结点都存有相邻叶子结点的指针，并根据关键字的按顺序链接。

B+树和B树的区别：

• B+树的叶子节点全部位于同一层，所以数据的查询时间复杂度固定为O(logn)；而B树查询时间复杂度不固定，最坏为O(logn)
• B+树的所有叶子节点按key的顺序串成链表，可以轻松地实现范围查询
• b+树的内部节点不存储数据，可实现单次磁盘 IO 的信息量比B树更大，相对而言可以减少IO次数

3.2 B+树添加和删除

B+树的添加与删除操作与B树相似。需要特别注意的是：B+树经过删除操作后，内部结点中存在的key，不一定在叶子结点中还存在对应的记录。

详细的介绍可参考这篇博客：B树和B+树的插入、删除图文详解

3.4 应用案例

• Mysql