B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树:

B树当中每个节点存储着一组数据,数据的数量由B树的来决定。

B树中的节点包含以下内容:

  • 大小(size):用来记录当前节点中元素的个数;

  • 关键字(key):B树是有序集合,关键字是可比的,用于在集合中定位卫星数据;

  • 是否为叶子节点(leaf):节点类型可以分为内部节点和叶子节点。

  • 孩子节点(children):如果当前节点是一个内部节点的话,那么就有更加底层的孩子节点。如果是叶子节点。那就没有孩子节点。孩子节点的数量总是比数据的数量多一个。

对于一个度数为N的B树,需要保持以下性质:

  • 一个节点中的数据量不小于N-1并且不大于2N-1,一个例外就是根节点可以包含小于N-1数量的数据;

  • 所有的叶子节点高度相等;

  • 在节点中,所有的数据关键字保持递增关系(key[0] < … < key[size-1]);

  • 对于一个孩子节点children[i],children[i]子树中所有关键大于key[i-1]并且小于key[i](key[-1]=-∞,key[size]=+∞)。

度数小于2的B树是没有意义的,因此度数最小的取值为2。完整的B树实现见Gist

节点定义

B树中不存在循环引用,因此可以大胆使用shared_ptr来代替原生指针,简化析构操作。B树的拷贝可以通过递归进行,因此数据结构地拷贝也就简单了很多。

struct Node
{
	bool _leaf;
	int _size;
	vector<Key> _keys = vector<Key>(2*N-1);
	vector<Value> _values = vector<Value>(2*N-1);
	vector<shared_ptr<Node>> _children = vector<shared_ptr<Node>>(2*N);
	Node() = default;
	Node(const Node &node): _leaf(node._leaf), _size(node._size), _keys(node._keys), _values(node._values)
	{
		if (!_leaf)
			for (int i = 0; i <= _size; i++)
				_children[i] = std::make_shared<Node>(*node._children[i]);
	}
};

创建

创建一个空地叶子结点,作为根节点。

BTree()
{
	root = std::make_shared<Node>();
	root->_leaf = true;
	root->_size = 0;
}

查找

如果在当前节点找到关键字,返回卫星数据指针。如果没有找到关键字,那么需要检查当前节点是否为叶节点,如果是叶节点,那么说明关键字不存在,返回指针,如果是内部节点,那么在子树中查找关键字。

Value* find(shared_ptr<Node> node, Key key)
{
	// search key in node
	int i = 0;
	while (i < node->_size && key > node->_keys[i])
		i++;
	if (i < node->_size && key == node->_keys[i])
		return &node->_values[i];
	else if (node->_leaf)
		return nullptr;
	else return find(node->_children[i], key);
}

分裂

当一个节点数据量到达2N-1时后,如果想要继续插入,就需要对节点进行分裂。把孩子节点中间元素提升到父节点中,然后产生两个新的孩子节点分别插入中间元素两侧。

// split a full node (child.size == 2*N-1)
void split(shared_ptr<Node> parent, int i, shared_ptr<Node> child)
{
	shared_ptr<Node> nchild = std::make_shared<Node>();
	nchild->_leaf = child->_leaf;
	nchild->_size = child->_size = N-1;
	// move k-v
	for (int j = 0; j < N-1; j++) {
		nchild->_keys[j] = child->_keys[j + N];
		nchild->_values[j] = child->_values[j + N];
	}
	// move children
	if (!child->_leaf)
		for (int j = 0; j < N; j++)
			nchild->_children[j] = child->_children[j + N];
	// move child->key[N-1] up
	for (int j = parent->_size; j > i; j--) {
		parent->_keys[j] = parent->_keys[j-1];
		parent->_values[j] = parent->_values[j-1];
		parent->_children[j+1] = parent->_children[j];
	}
	parent->_keys[i] = child->_keys[N-1];
	parent->_values[i] = child->_values[N-1];
	parent->_children[i+1] = nchild;
	parent->_size++;
}

合并

合并操作是分裂操作的逆向过程。

// combine children[i] and children[i+1]
void combine(shared_ptr<Node> parent, int i)
{
	shared_ptr<Node> prev = parent->_children[i];
	shared_ptr<Node> next = parent->_children[i+1];
	// move parent->key[i] down
	prev->_keys[prev->_size] = parent->_keys[i];
	prev->_values[prev->_size] = parent->_values[i];
	prev->_size++;
	// move k-v from next to prev
	for (int j = 0; j < next->_size; j++) {
		prev->_keys[j + prev->_size] = next->_keys[j];
		prev->_values[j + prev->_size] = next->_values[j];
	}
	if (!prev->_leaf)
		for (int j = 0; j <= next->_size; j++)
			prev->_children[j + prev->_size] = next->_children[j];
	prev->_size += next->_size;
	// remove parent->key[i]
	parent->_size--;
	for (int j = i; j < parent->_size; j++) {
		parent->_keys[j] = parent->_keys[j+1];
		parent->_values[j] = parent->_values[j+1];
		parent->_children[j+1] = parent->_children[j+2];
	}
}

插入

当根节点满了,需要创建一个新的根节点,然后将旧的根节点分裂,成为新的根节点的子节点。

// insert k-v in root node
void insert(Key key, Value value)
{
	shared_ptr<Node> ptr = root;
	if (ptr->_size == 2*N-1) {	// split root node
		root = std::make_shared<Node>();
		root->_leaf = false;
		root->_size = 0;
		root->_children[0] = ptr;
		split(root, 0, ptr);
		insert(root, key, value);
	} else insert(root, key, value);
}
  • 插入叶节点:直接插入即可。

  • 插入内部节点:首先,找到新关键字所在的子节点,如果子节点满,进行分裂。然后插入到合适的子节点中。

void insert(shared_ptr<Node> node, Key key, Value value)
{
	// find insert position
	int i = 0;
	while (i < node->_size && key > node->_keys[i])
		i++;
	if (node->_leaf) {	// insert k-v in a leaf
		for (int j = node->_size; j > i; j--) {
			node->_keys[j] = node->_keys[j-1];
			node->_values[j] = node->_values[j-1];
		}
		node->_keys[i] = key;
		node->_values[i] = value;
		node->_size++;
	} else {			// insert k-v in subnode
		shared_ptr<Node> ptr = node->_children[i];
		if (ptr->_size == 2*N-1) {
			split(node, i, ptr);
			if (key > node->_keys[i])
				i++;
		}
		insert(node->_children[i], key, value);
	}
}

删除

和插入操作一样,删除操作也是自顶向下对B树进行调整,必须保证要删除的关键字位于B树中,否则会产生意想不到的后果,对于删除操作,处理方式如下:

  • 情况1,当前节点是叶子节点,找到关键字:直接删除关键字即可。

  • 情况2,当前节点是内部节点,找到关键字key[i]:

    • 情况2a,如果关键字的左孩节点children[i]->size>=N:用children[i]中的最大元素(关键字的前驱)代替关键字,然后在children[i]中删除最大元素。

    • 情况2b,如果关键字的右孩节点children[i+1]->size>=N:用children[i+1]中的最小元素(关键字的后继)代替关键字,然后在children[i+1]中删除最小元素

    • 情况2c,如果关键字的左右两个子节点都小于N-1:这时可以合并两个子节点,于是关键字key[i]落入新合并成的节点中,接着在新的节点中删除关键字。

  • 情况3,当前节点是内部节点,找到关键字所在的子树children[i]:如果children[i]->size<N,那么还需要进行一些调整之后再删除。

    • 情况3a,如果children[i]的某个相邻兄弟节点children[x]->size>=N:通过移动操作,使得children[x]元素数量减一,children[i]元素数量加一。

    • 情况3b,如果children[i]的所有相邻兄弟节点children[x]->size < N:将children[i]和任意一个children[x]合并。(到底和左边的合并好还是右边的好,好纠结~)

// remove key from node, key must be in node
void remove(shared_ptr<Node> node, Key key)
{
	// find delete position
	int i = 0;
	while (i < node->_size && key > node->_keys[i])
		i++;
	if (node->_leaf) {										// case 1: remove k-v from leaf
		node->_size--;
		for (int j = i; j < node->_size; j++) {
			node->_keys[j] = node->_keys[j+1];
			node->_values[j] = node->_values[j+1];
		}
	} else if (i < node->_size && key == node->_keys[i]) {	// case 2: find key in internal node
		shared_ptr<Node> prevChild = node->_children[i];
		shared_ptr<Node> nextChild = node->_children[i+1];
		if (prevChild->_size >= N) {						// case 2a: move precursor to the position of key
			shared_ptr<Node> maxNode = max(prevChild);
			node->_keys[i] = maxNode->_keys[maxNode->_size-1];
			node->_values[i] = maxNode->_values[maxNode->_size-1];
			remove(prevChild, maxNode->_keys[maxNode->_size-1]);
		} else if (nextChild->_size >= N) {					// case 2b: move successor to the position of key
			shared_ptr<Node> minNode = min(nextChild);
			node->_keys[i] = minNode->_keys[0];
			node->_values[i] = minNode->_values[0];
			remove(nextChild, minNode->_keys[0]);
		} else {											// case 2c: combine previous child and next child
			combine(node, i);
			remove(node->_children[i], key);
		}
	} else {														// case 3
		shared_ptr<Node> subNode = node->_children[i];
		if (subNode->_size < N) {
			shared_ptr<Node> prevBrother, nextBrother;
			if (i > 0)				prevBrother = node->_children[i-1];
			if (i < node->_size)	nextBrother = node->_children[i+1];
			if (prevBrother && prevBrother->_size >= N) {			// case 3a
				// remove node->key[i] into subNode
				for (int j = subNode->_size; j > 0; j--) {
					subNode->_keys[j] = subNode->_keys[j-1];
					subNode->_values[j] = subNode->_values[j-1];
				}
				if (!subNode->_leaf)
					for (int j = subNode->_size; j >= 0; j--)
						subNode->_children[j+1] = subNode->_children[j];
				subNode->_keys[0] = node->_keys[i-1];
				subNode->_values[0] = node->_values[i-1];
				subNode->_children[0] = prevBrother->_children[prevBrother->_size];
				subNode->_size++;
				// remove prevBrother->key[prevBrother->size-1] into node
				node->_keys[i-1] = prevBrother->_keys[prevBrother->_size-1];
				node->_values[i-1] = prevBrother->_values[prevBrother->_size-1];
				prevBrother->_size--;
			} else if (nextBrother && nextBrother->_size >= N) {	// case 3a	
				// remove node->key[i] into subNode
				subNode->_keys[subNode->_size] = node->_keys[i];
				subNode->_values[subNode->_size] = node->_values[i];
				subNode->_children[subNode->_size+1] = nextBrother->_children[0];
				subNode->_size++;
				// remove nextBrother->key[0] into node
				node->_keys[i] = nextBrother->_keys[0];
				node->_values[i] = nextBrother->_values[0];
				nextBrother->_size--;
				for (int j = 0; j < nextBrother->_size; j++) {
					nextBrother->_keys[j] = nextBrother->_keys[j+1];
					nextBrother->_values[j] = nextBrother->_values[j+1];
				}
				if (!nextBrother->_leaf)
					for (int j = 0; j <= nextBrother->_size; j++)
						nextBrother->_children[j] = nextBrother->_children[j+1];
			} else if (nextBrother) {	// case 3b: combine child[i] and child[i+1]
				combine(node, i);
			} else {					// case 3b: combine child[i-1] and child[i]
				i--;
				combine(node, i);
			}
		}
		remove(node->_children[i], key);
	}
}

随着删除不断进行,会出现根节点变为空的情况,这时候需要把空的根节点删除。如果B树中的元素被全部删除,那么需要重新创建一个根节点。由于删除过程会改变B树结构,需要再删除前检查关键字是否存在。

void remove(const Key &key)
{
	if (find(root, key))
		remove(root, key);
	if (root->_size == 0)
		root = root->_children[0];
	if (root == nullptr) {
		root = std::make_shared<Node>();
		root->_leaf = true;
		root->_size = 0;
	}
}