首页计算机科学C++零声笔记

# B 树

多路平衡 搜索树
索引在 内存 ， 数据 映射 磁盘( 磁盘页 4K 的整数倍)，
多路，降低红黑树和二叉树的 层 高， 降低IO 访问次数

# B 树和 B + 树

  • B树 节点中即 存储数据 信息，也会 存储索引 信息
  • B+树 节点中即存储数据信息，也会存储索引信息， 非叶子 节点 只有索引 信息
  • B+ 树 期待更 少 的磁盘 IO - 将索引信息和数据信息进行 分层 管理
  • B+树 加载到内存的 无效 数据 更少

# etcd

强 一致性、 高 可用性的数据访问服务，用来存储 少量重要 的数据。刷盘的时候更快，B 树和 B + 树都是 映射着磁盘页

  • 内存中使用 B 树
  • 磁盘中使用 B + 树

# MySQL

索引：索引对应一个 B + 树，支持的行锁，MySQL 拥有缓存

  • 聚集索引 B + 树 ： 主键索引
  • 辅助索引：先通过辅助索引 获取聚集索引 ，然后根据聚集索引获得叶子结点记录的信息

索引覆盖: select 查询具体数据时，这个数据恰好在辅助索引时，就可以获得所有数据，不用再到聚集索引

最左匹配规则：组合索引时，根据从左到右顺序依次匹配。

事务：服务器和数据库可能需要 多条语句 实现某个逻辑，多个数据库请求。数据库提供一个 机制 ，让多个语句一同执行，当查询的数据表 不存在 时，对数据表的查询和插入就 不再执行

# 时间轮

处理 海量定时任务 ，多线程下定时器设计，按照执行顺序进行组织 0 (1), 分层 的目的 减少内存开销 。只关注 最近60秒 要执行的任务

  • Linux内核
  • kafka
  • skynet
  • netty

# 跳表

多层级结构，多层级的 有序链表 ，从上往下跳，随机性的数据结构 0(log2n) (以 2 为低)

  • redis : kv v-> zset 有序集合，score : 有序， member 确保唯一
  • levelrocksdb , rocksdb (存储引擎)

理想跳表

跳表插入

跳表索引失衡

B+树结构

# 引入

二叉树层高，对比次数多，找到下一个节点多，
数据存储到磁盘，其读取到内存， 读取 效率 下降 。若每个节点都存储在磁盘，每次对比后找下一个节点都是一次磁盘寻址。二叉树就极其耗时。
急需降低层高的数据存储，使用 多叉
B 树，所有的 叶子节点在同一层

磁盘寻址

# 性质

  • 每个节点最多拥有 M颗 子树
  • 根 节点 至少 拥有 两 颗子树
  • 除根节点以外，其余 每个分支 节点 至少 拥有 M/2颗 子树
  • 所有的 叶节点 都在同 一层 上
  • 有 K颗子 树的分支结点则存在 k-1 个关键字，关键字按照 递增 顺序进行排序
  • 关键字数量满足 ceil(M/2)-1 <=n <=M-1 ceil向上取整 （删除时注意)

# B 树 B + 树区别

  • B 树: 所有节点存储数据 (部分数据在内存，部分节点在磁盘)
  • B + 树: 叶子节点存储数据 ， 内节点索引引用存储内存 ( B+树 索引在 内存数量 > B树 ) 提高索引效率，常用与索引磁盘数据大量数据 ( MySql ， MongoDB 等)

# 添加

  • 设置 B树 的 M 为 6 ，最多为 6 个子树
  • 添加数据为 A-Z 依次加入
  • 根节点分裂：当添加的节点 F 时，节点数 超过6 ，将进行节点分裂，以原有节点 中心C 为中心节点分为左右结点进行分裂（ 先分裂再添加 )

节点添加

  • 叶节点分裂 ：继续添加数据：

节点添加

  • 当加到 L 时原有达到 分裂条件 ， 先分裂 ，让中心节点 I上移

根节点拆分

  • 在往后的 添加过程 中，若 节点也满 了，将如第一部分对 节点进行分裂 ， 先分裂后添加

image-20230629091213538

# 删除

删除条件：

  • idx 子树， ceil(m/2) -1
    • 借位
      • 从 idx -1 大于 ceil(m/2) -1
      • 从 idx +1 大于 ceil(m/2) -1
    • 合并
      • {childs[idx].keys} {keys[idx]} {childs[idx+1].keys}

  • 节点归并
    节点归并

  • 若关键字在 叶子节点 中， 直接删除 即可
    删除节点

  • 若删除节点后不满足性质 关键字 数量满足 ceil(M/2)-1 <=n <=M-1 先合并或借位再删除
    不满足关键词

    • 要删除 节点A ，其 父节点 ，若其 树=M/2-1 需要 借位 。避免 后面节点资源不足 (因为删除 A 之后需要合并，会导致资源不足)。将 I节点 借过去之后，其 I节点 的有节点 最小 将随着 I 节点的变化变为 左边的最大 。并将 右边的L 替代为 根节点 ，（也是为了下面合并之后其父节点仅剩 F 自己的提前安排）如下:
      借根节点I
    • 删除 A 之后，不满足性质，则 进行合并 ，将其 父与相邻相邻节点 进行合并。 先合并再删除
      合并
    • 删除节点A
      删除节点A

  • 删除节点 B，

    • 其 父节点和删除的节点 都满足条件
      删除节点B
    • 直接删除
      B节点已删除

  • 删除节点D

    • 删除 D 之后，其节点不满足最后一条性质 ceil(M/2)-1 <=n <=M-1 , 其父节点符合条件，不用借位， 直接合并
      直接合并
    • 删除 D 节点

    删除D节点

  • 删除E节点 ，其 父节点 满足 树=M/2-1 ，需要先进行 借位 ，在进行 合并删除 ，由于 右边 也等于 M/2-1 ， 无法 进行 借位 ，则进行对 父节点进行合并
    需要合并

    • 合并

    合并

    • 直接删除 E 节点

    删除节点E

  • 删除 F 节点，删除后满足所有添加，直接删除即可

​ 删除节点F

  • 删除 G 之后，其所在节点不满足条件，则合并节点，在删除

    • 合并节点

    删除节点G

    • 删除

    删除节点G之后

# 插入

  • 找到 对应的节点
  • 对节点的 key对比 ，找到 合适的位置
  • 插入的数是 插在叶子节点上面

# 代码实现

// 根节点分裂

// 1 - 3 特殊情况

// 其它一分为 2

// 根节点不同

// 分裂：添加

// 合并与错位：删除

// 合并

# B 树定义

//1, 定义 B/B - 树
//#define SUM_M 3
typedef int KEY_VALUE;
//2, B 树结构体
typedef struct _btree_node
{
    // int keys[2*SUM_M -1];   // 5
    // struct _btree_node *childrens[2*SUM_M]; //6
    KEY_VALUE *keys;   // 5
    struct _btree_node **childrens; //6
    int num;  // 存储多少数据
    int leaf; // 是否为叶子节点 0 为内节点
}btree_node;
// 定义根节点
typedef struct _btree
{
    struct _btree_node *root;
    int t;  // 定义支持节点个数
} btree;
# 创建节点
// 创建节点，叶节点
btree_node *btree_create_node(int t,int leaf)
{
    btree_node* node = (btree_node*)calloc(1,sizeof(btree_node));  // 自带初始化为 0  calloc
    if(node == NULL)
    {
        assert(0);
        return NULL; // 出错是内存不够用，
    }
    node->leaf = leaf;
    node->keys = (KEY_VALUE*)calloc(1,(2*t -1)*sizeof(KEY_VALUE));
    node->childrens = (btree_node**)calloc(1,(2*t)*sizeof(btree_node*));
    node->num = 0;
    return node;
}
void btree_create(btree *T, int t) {
	T->t = t;
	
	btree_node *x = btree_create_node(t,1);
	T->root = x;
}
# 销毁节点
// 销毁节点
void btree_destory_node(btree_node* node)
{
    assert(node);
    free(node->childrens);
    free(node->keys);
    free(node);
}
# 节点分裂
结点分裂
// 分裂
// 参数 T 代表这棵树 x 为需要分裂的父节点 i 为 x 的节点的第几个子树 (从 0 开始)
void btree_split_child(btree *T,btree_node *x,int idx)
{
    int t = T->t;
    // 把需要斐裂的节点全部赋值给了 Z
    btree_node *y = x->childrens[idx];  // 根据条件找到需要分裂的节点
    btree_node *z = btree_create_node(t,y->leaf);
    // Z 放前面
    z->num = t -1;  // 复制两个
    //1 把 y 的节点右边复制给 z 节点（把 y 和 z copy 到 z）
    int j;
    for(j = 0;j< t-1;j++)
    {
        z->keys[j] = y->keys[t+j];
    }
    // 如果是内节点，把 y 的的 y 和 z 子节点叶复制过去
    if(y->leaf == 0)
    {
        for(j = 0;j<t;j++)
        {
            z->childrens[j] = y->childrens[t +j];
        }
    }
    y->num = t -1; // 修改为 2
    //2，将 X 的节点向后移动，
    // 当 x 放上去，若 x 后面还有数据
    for(j = x->num;j >= idx+1;j--)
    {
        x->childrens[j+1] = x->childrens[j]; // 向后移动
    }
    //3 x 在定义的节点子孩子
    x->childrens[idx+1] = z;
    //4 将 x 节点里面的 key 值进行交换进行往后移
    for(j = x->num-1;j>=idx;j--)
    {
        x->keys[j+1] = x->keys[j];
    }
    // 5，x 中间节点向上
    x->keys[idx] = y->keys[t-1];
    //x 的节点 + 1
    x->num += 1;
}
# 插入未满节点
// 插入进去一个未满的节点  x 为要插入节点
void btree_insert_notfull(btree* T,btree_node *x,KEY_VALUE key)
{
    int i = x->num -1;
    // 如果不是叶子节点就往下递归，如果是叶子节点，再插入
    if(x->leaf == 1)
    {
        // 插入
        // 当 i 大于等于 0 并且 x 对应的 key 值比 k 大时，向前移动 i--
        //x 的值后移，为存储 key 留下空间
        while (i>=0 && x->keys[i] > key)
        {
            /* code */
            x->keys[i+1] = x->keys[i];
            i--;
        }
        // 找到插入的位置 (while 循环的再次 i--，需要加 1)
        x->keys[i+1] = key;
        x->num +=1;
    }
    else
    {
        // 继续递归
        // 找到对应 key 值应该再那个子树上面
        while(i>=0 && x->keys[i] > key)
        {
            i--;
        }
        // 如果子树是满的
        if(x->childrens[i+1]->num == 2*(T->t)-1) 
        {
            // 进行分裂
            btree_split_child(T,x,i+1);
            // 如果 key 大于 keys 后的节点，++
            if(key>x->keys[i+1])
            {
                i++;
            }
            
        }
        // 进行向下递归
        btree_insert_notfull(T,x->childrens[i+1],key);
    }
}
# 插入节点
// 根节点如何分裂，一分为三
void btree_insert(btree* T,int key)
{
    btree_node *r = T->root;
    if(r->num == 2*SUM_M-1) // 
    {
        // 创建新节点
        btree_node* node = btree_create_node(0); //0 为非叶子节点
        T->root = node;  // 将根节点指向此
        node->childrens[0] = r;  // 根节点的子节点为 r
        btree_split_child(T,node,0); // 分裂完成之后
        // 再进行插入
        
        int i = 0;
        // 判断 node 的值找到 key 对应的 node 子节点位置
		if (node->keys[0] < key) 
        {
            i++;
        }
        // 插入非满节点
		btree_insert_nonfull(T, node->childrens[i], key);
    }
    else
    {
        btree_insert_nonfull(T, r, key);
    }
}
# 节点合并
// 合并
//x 为当前的节点（即需要删除节点的父节点)，idx 要删除的节点位置
void btree_merge(btree *T,btree_node *x,int idx)
{
    btree_node *left = x->childrens[idx]; // 左
    btree_node *right = x->childrens[idx+1]; // 右
    
    left->keys[T->t-1] = x->keys[idx]; // 将 x 的 C 拷贝到子节点
     // 开始循环
    int i = 0;
     // 将 x 的右边的值复制到左边
    for(i=0;i<T->t-1;i++)
    {
        left->keys[T->t+i] = right->keys[i];
    }
    // 判断是不是叶子节点
    // 将右边的子树也全部拷贝到左边
    if(!left->leaf)
    {
        for(i=0;i<T->t;i++)
        {
            left->childrens[T->t+i]= right->childrens[i];
        }
    }
    left->num +=T->t;
    btree_destory_node(right);// 右边节点已经全部赋值到左边，右边的清楚释放
    // 删除的父节点少了一个节点需要，后面的节点需要前移
    // 从 1 开始
    for(i=idx+1;i<x->num;i++)
    {
        x->keys[i-1]=x->keys[i];
        x->childrens[i] = x->childrens[i+1];
    }
    x->childrens[i+1] = NULL;
	x->num -= 1;
    // 若为根
	if (x->num == 0) {
		T->root = left;
		btree_destory_node(x);
	}
}
# 节点输出
// B 树输出
// T B 树，node 为输出的节点，根节点 T.root, layer 层
void btree_print(btree *T, btree_node *node, int layer)
{
	btree_node* p = node;
	int i;
    // 如果 p 不为空
	if(p)
    {
		printf("\nlayer = %d keynum = %d is_leaf = %d\n", layer, p->num, p->leaf);
		// 对 node 的节点全部输出
        for(i = 0; i < node->num; i++)
			printf("%c ", p->keys[i]);
		printf("\n");
#if 0
		printf("%p\n", p);
		for(i = 0; i <= 2 * T->t; i++)
			printf("%p ", p->childrens[i]);
		printf("\n");
#endif
        // 层数 ++
		layer++;
        // 子节点进行遍历递归循环
		for(i = 0; i <= p->num; i++)
			if(p->childrens[i])
				btree_print(T, p->childrens[i], layer);
	}
	else printf("the tree is empty\n");
}
# 节点删除
结点删除
// B 树删除
// 1，递归找到对应的子树
// 2,  * `idx` 子树，`ceil (m/2) -1`
/*   * `借位`
        * 从 `idx -1` 大于 `ceil (m/2) -1`
        * 从 `idx +1` 大于 `ceil (m/2) -1`
    * 合并
        * `{childs [idx].keys} {keys [idx]} {childs [idx+1].keys}`
*/
//node 要删除的节点，key 要删除的关键字
void btree_delete_key(btree* T,btree_node *node,KEY_VALUE key)
{
    // 如果输出的节点为空
    if(node == NULL)
    {
        return ;
    }
    // 找节点
    int idx = 0 ,i;
    while(idx < node->num && key > node->keys[idx])
    {
        idx ++;
    }
    // 找到节点
    if(idx <node->num && key == node->keys[idx])
    {
        //1， 如果节点是叶节点
        if(node->leaf)
        {
            // 直接删除
            // 将删除之后的节点前移
            for (i = idx;i < node->num-1;i ++) {
				node->keys[i] = node->keys[i+1];
			}
            // 初始化最后一个删除节点的空间
            node->keys[node->num - 1] = 0;
			node->num--;
            // 如果节点为 root 释放空间
            if (node->num == 0) 
            { //root
				free(node);
				T->root = NULL;
			}
            return ;
        }
        else if(node->childrens[idx]->num >= T->t)
        {
            // 2 (不完善图例)，如果不是叶节点 像前面 idx 借
            btree_node *left = node->childrens[idx];
			node->keys[idx] = left->keys[left->num - 1];
			btree_delete_key(T, left, left->keys[left->num - 1]);
        }
        else if(node->childrens[idx+1]->num >= T->t)
        {
            //3， 向后面借
            btree_node *right = node->childrens[idx+1];
			node->keys[idx] = right->keys[0];
			btree_delete_key(T, right, right->keys[0]);
        }
        else
        {
            //2, 情况 数量小于 3 SUM_M 合并 再调用删除
            btree_merge(T, node, idx);
			btree_delete_key(T, node->childrens[idx], key);
        }
    }
    // 左右借孩子
    else //idx < node-> num 但是 key != node->keys [idx], 需要在其孩子中寻找
    {
        // 4, 锁定到孩子的节点
        btree_node *child = node->childrens[idx];
        // 如果孩子的结点为空
		if (child == NULL) 
        {
			printf("Cannot del key = %d\n", key);
			return ;
		}
        // 如果孩子的数量为 2
        if (child->num == T->t - 1) {
            // 定义此节点的左右孩子
			btree_node *left = NULL;
			btree_node *right = NULL;
            // 左孩子
			if (idx - 1 >= 0)
				left = node->childrens[idx-1];
            // 右孩子
			if (idx + 1 <= node->num) 
				right = node->childrens[idx+1];
            // 如果左 / 右孩子节点数量 > 3
			if ((left && left->num >= T->t) ||
				(right && right->num >= T->t)) {
                // 记录左右结点的谁的数量大，
				int richR = 0;  
				if (right) richR = 1;
                // 1，是右边大，0 是右边小
				if (left && right) richR = (right->num > left->num) ? 1 : 0;
                // 如果右节点的数量大于 3 并且右边数量大 ，从右边借
				if (right && right->num >= T->t && richR) 
                {    //borrow from next 从右边借
                    // 先将 node 的值复制到 child 的后面
					child->keys[child->num] = node->keys[idx];
                    // 孩子节点的孩子最后叶等于右边的第一个
					child->childrens[child->num+1] = right->childrens[0];
                    // 孩子的数量 ++
					child->num ++;
                    //node 节点的最后一个为 rigth 节点的第一个
					node->keys[idx] = right->keys[0];
                    // 右孩子节点 (由于第一个 keys 移动，全部向前移动)
					for (i = 0;i < right->num - 1;i ++) 
                    {
						right->keys[i] = right->keys[i+1];
						right->childrens[i] = right->childrens[i+1];
					}
                    // 全部前移之后，右节点的最后一个对其进行销毁
					right->keys[right->num-1] = 0;
					right->childrens[right->num-1] = right->childrens[right->num];
					right->childrens[right->num] = NULL;
                    // 右节点数量 - 1 
					right->num --;
					
				} 
                else  // 如果没有右节点或者数量不足 3 或者右边数量小，考虑左边，从左边借
                { //borrow from prev
                    // 孩子节点全部后移
					for (i = child->num;i > 0;i --) {
						child->keys[i] = child->keys[i-1];
						child->childrens[i+1] = child->childrens[i];
					}
                    // 将孩子的第一个指向左边的最后一个
					child->childrens[1] = child->childrens[0];
					child->childrens[0] = left->childrens[left->num];
					child->keys[0] = node->keys[idx-1];
					// 孩子的数量 ++
					child->num ++;
                    //keys 赋值
					node->keys[idx-1] = left->keys[left->num-1];
                    // 最左节点最后一个进行初始化为 NULL
					left->keys[left->num-1] = 0;
					left->childrens[left->num] = NULL;
					left->num --;
				}
			} 
            // 如果其左节点 / 右节点为 2 时 进行合并
            else if ((!left || (left->num == T->t - 1))
				&& (!right || (right->num == T->t - 1))) 
            {
				if (left && left->num == T->t - 1) 
                {
					btree_merge(T, node, idx-1);					
					child = left;
				} else if (right && right->num == T->t - 1) 
                {
					btree_merge(T, node, idx);
				}
			}
		}
        // 将其孩子节点调用删除函数
        btree_delete_key(T, child, key);
    }
   
}
int btree_delete(btree *T, KEY_VALUE key) {
	if (!T->root) return -1;
	btree_delete_key(T, T->root, key);
	return 0;
}
# 测试函数
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
int main() {
	btree T = {0};
    // 创建节点
	btree_create(&T, 3);
	srand(48); // 随机数
	int i = 0;
	char key[26] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // 将 26 英文字母插入
	for (i = 0;i < 26;i ++) {
		//key[i] = rand() % 1000;
		printf("%c ", key[i]);
		btree_insert(&T, key[i]);
	}
    // 输出
	btree_print(&T, T.root, 0);
	for (i = 0;i < 26;i ++) {
		printf("\n---------------------------------\n");
		btree_delete(&T, key[25-i]);
		//btree_traverse(T.root);
		btree_print(&T, T.root, 0);
	}
	
}