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/