你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

c/c++linux后台开发学习笔记 1.1.2 b树/b+树

2021-11-23 5:35:44

b/b+树的特点

  • 有序
  • 平衡(到任意叶子节点的距离相等)
  • 高度低,减少磁盘IO,B+用于数据库存储,B树只用于学术研究

b树与b+树的区别

  • b树在中间节点和叶子节点上都存储数据
  • b+树只在叶子节点上存数据,并且将叶子节点连起来形成链表,方便范围查询

b树定义

  • 一个t阶b树,每个节点(除了根节点)至少有t-1个key,最多有2t-1个可以,子节点的个数是key数+1
  • 根节点至少有一个key

b树插入

总是从叶子插入,增高是因为叶子分裂

def btree_insert(root, k):
	if root is full:
		create new empty root
		split old root
		x = whatever node that contains k
	else:
		x = root
	# 不变量:x is not full
	while x is not leaf:
		y = x's child that contains k
		if y is full:  # y.size == 2t-1
			split y    # will move a key into x
			y = whatever node that contains k
		x = y
	insert x

b树删除

# 除非node是root,否则node必须拥有至少t个key
def btree_delete(node, k):
	i = index of k first key in node.key that is >= k
	if k is in node.keys:
		if node is leaf:
			delete k from node
		else # node is not leaf
			if size of left child of k (index = i) >= t:
				# copy prev key from left child, then recursively delete that key from left child
				prev_k = last key of left child
				node.keys[i] = prev_k 
				btree_delete(left child, prev_k )
			elif size of right child of k (index = i+1) >= t:
				# copy next key from right child, then recursively delete that key from right child
				next_k = first key of right child
				node.keys[i] = next_k
				btree_delete(right child, next_k)
			else:
				merge(k, left child, right child) #push k down, merged node should be the prev left child (index = i)
				btree_delete(merged node, k)
	else: # k is in subtree
		c = node.children[i] # c is the subtree that should contains k
		if not c: return
		if c has only t-1 keys: # need to ensure c has at least t keys
			if a sibling of c (say y) has at least t keys:
				move first/last key from y to node.key[i], move node.key[i] to c
			else:
				merge c with one of its sibling # depending on if they exist
		btree_delete(c, k)
			

参考资料

[1] 零声学院c/c++linux后台开发1.1.2
[2] https://www.geeksforgeeks.org/delete-operation-in-b-tree/