B树
提示
- B树特点：B树是一种自平衡的多路搜索树，每个节点可包含多个键值和子节点，高度平衡，降低了树的高度，提高访问效率。
- B树的优势：适用于大量数据存储和访问，减少了磁盘I/O操作，比如数据库和文件系统中，尤其适合辅助存储设备。
- 操作和性能：B树支持高效的插入、删除和搜索操作，所有操作的时间复杂度均为Θ(log n)，使其在处理大量数据时更高效。
B树是一种特殊的自平衡搜索树，其中每个节点可以包含多个键，并且可以拥有多于两个的子节点。它是二叉搜索树的一种泛化形式。
它也被称为高度平衡的 m 叉树。
为什么需要 B树 数据结构？
随着对于访问物理存储介质（如硬盘）的时间需求的增加，B树的需求应运而生。辅助存储设备容量大但速度慢。因此，有必要开发这种能够最小化磁盘访问的数据结构。
其他数据结构，如二叉搜索树、AVL 树、红黑树等，每个节点只能存储一个键。如果你要存储大量的键，那么这些树的高度会变得非常大，访问时间也会增加。
然而，B树可以在一个节点中存储多个键，并且可以拥有多个子节点。这显著降低了树的高度，从而允许更快的磁盘访问。
B树的属性
- 对于每个节点
x，键以递增顺序存储。 - 在每个节点中，有一个布尔值
x.leaf，如果x是叶子节点，则为真。 - 如果
n是树的阶，每个内部节点最多可以包含n - 1个键以及指向每个子节点的指针。 - 除根节点外的每个节点最多可以有 n 个子节点，至少有
n/2个子节点。 - 所有叶子节点具有相同的深度（即树的高度 h）。
- 根节点至少有 2 个子节点，并且至少包含 1 个键。
- 如果
n ≥ 1，那么对于任何高度为 h、最小度t ≥ 2的 n 键 B树，有h ≥ logt (n+1)/2。
对 B树的操作
在 B树中搜索一个元素
在 B树中搜索一个元素是在二叉搜索树中搜索元素的泛化形式。遵循以下步骤。
- 从根节点开始，将 k 与节点的第一个键进行比较。
如果
k = 节点的第一个键，返回节点和索引。 - 如果
k.leaf = true，返回NULL（即未找到）。 - 如果
k < 根节点的第一个键，递归地搜索这个键的左子节点。 - 如果当前节点中有多于一个键并且
k > 第一个键，将 k 与节点中的下一个键进行比较。 如果k < 下一个键，搜索这个键的左子节点（即 k 位于第一个和第二个键之间）。 否则，搜索这个键的右子节点。 - 重复步骤 1 到 4，直到到达叶子节点。
搜索示例
-
让我们在下面的度为 3 的树中搜索键
k = 17。
-
在根节点未找到
k，因此与根键进行比较。
-
由于
k > 11，转向根节点的右子节点。
-
将 k 与 16 进行比较。由于
k > 16，
将 k 与下一个键 18 进行比较。
-
由于
k < 18，k 位于 16 和 18 之间。在 16 的右子节点或 18 的左子节点中搜索。
-
找到了 k。
搜索元素的算法
BtreeSearch(x, k)
i = 1
while i ≤ n[x] and k ≥ keyi[x] // n[x] 表示 x 节点中的键数量
do i = i + 1
if i n[x] and k = keyi[x]
then return (x, i)
if leaf [x]
then return NIL
else
return BtreeSearch(ci[x], k)
要了解更多关于不同 B树操作的信息，请访问
Python、Java 和 C/C++ 中的 B树操作代码
# 在 Python 中对 B树进行键搜索
# 创建一个节点
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []
# 树
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t
# 插入节点
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
# 插入非满节点
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)
# 分裂子节点
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.child = y.child[t: 2 * t]
y.child = y.child[0: t - 1]
# 打印树
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)
# 在树中搜索键
def search_key(self, k, x=None):
if x is not None:
i = 0
while i < len(x.keys) and k > x.keys[i][0]:
i += 1
if i < len(x.keys) and k == x.keys[i][0]:
return (x, i)
elif x.leaf:
return None
else:
return
self.search_key(k, x.child[i])
else:
return self.search_key(k, self.root)
def main():
B = BTree(3)
for i in range(10):
B.insert((i, 2 * i))
B.print_tree(B.root)
if B.search_key(8) is not None:
print("\n找到了")
else:
print("\n未找到")
if __name__ == '__main__':
main()
// 在 Java 中搜索 B 树上的键
public class BTree {
private int T;
// 节点创建
public class Node {
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;
public int Find(int k) {
for (int i = 0; i < this.n; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}
public BTree(int t) {
T = t;
root = new Node();
root.n = 0;
root.leaf = true;
}
private Node root;
// 搜索键
private Node Search(Node x, int key) {
int i = 0;
if (x == null)
return x;
for (i = 0; i < x.n; i++) {
if (key < x.key[i]) {
break;
}
if (key == x.key[i]) {
return x;
}
}
if (x.leaf) {
return null;
} else {
return Search(x.child[i], key);
}
}
// 分裂节点
private void Split(Node x, int pos, Node y) {
Node z = new Node();
z.leaf = y.leaf;
z.n = T - 1;
for (int j = 0; j < T - 1; j++) {
z.key[j] = y.key[j + T];
}
if (!y.leaf) {
for (int j = 0; j < T; j++) {
z.child[j] = y.child[j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= pos + 1; j--) {
x.child[j + 1] = x.child[j];
}
x.child[pos + 1] = z;
for (int j = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}
// 插入值
public void Insert(final int key) {
Node r = root;
if (r.n == 2 * T - 1) {
Node s = new Node();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
Split(s, 0, r);
insertValue(s, key);
} else {
insertValue(r, key);
}
}
// 插入节点
final private void insertValue(Node x, int k) {
if (x.leaf) {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
x.key[i + 1] = x.key[i];
}
x.key[i + 1] = k;
x.n = x.n + 1;
} else {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
}
;
i++;
Node tmp = x.child[i];
if (tmp.n == 2 * T - 1) {
Split(x, i, tmp);
if (k > x.key[i]) {
i++;
}
}
insertValue(x.child[i], k);
}
}
public void Show() {
Show(root);
}
// 展示
private void Show(Node x) {
assert (x == null);
for (int i = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
}
if (!x.leaf) {
for (int i = 0; i < x.n + 1; i++) {
Show(x.child[i]);
}
}
}
// 检查是否存在
public boolean Contain(int k) {
if (this.Search(root, k) != null) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
BTree b = new BTree(3);
b.Insert(8);
b.Insert(9);
b.Insert(10);
b.Insert(11);
b.Insert(15);
b.Insert(20);
b.Insert(17);
b.Show();
if (b.Contain(12)) {
System.out.println("\n找到");
} else {
System.out.println("\n未找到");
}
;
}
}
// 在 C 中搜索 B 树上的键
#include <stdio.h>
#include <stdlib.h>
#define MAX 3
#define MIN 2
struct BTreeNode {
int val[MAX + 1], count;
struct BTreeNode *link[MAX + 1];
};
struct BTreeNode *root;
// 创建节点
struct BTreeNode *createNode(int val, struct BTreeNode *child) {
struct BTreeNode *newNode;
newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}
// 插入节点
void insertNode(int val, int pos, struct BTreeNode *node,
struct BTreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
}
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
}
// 分裂节点
void splitNode(int val, int *pval, int pos, struct BTreeNode *node,
struct BTreeNode *child, struct BTreeNode **newNode) {
int median, j;
if (pos > MIN)
median = MIN + 1;
else
median = MIN;
*newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
insertNode(val, pos, node, child);
} else {
insertNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}
// 设置值
int setValue(int val, int *pval,
struct BTreeNode *node, struct BTreeNode **child) {
int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
}
if (val < node->val[1]) {
pos = 0;
} else {
for (pos = node->count;
(val < node->val[pos] && pos > 1); pos--)
;
if (val == node->val[pos]) {
printf("不允许重复\n");
return 0;
}
}
if (setValue(val, pval, node->link[pos], child)) {
if (node->count < MAX) {
insertNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
// 插入值
void insert(int val) {
int flag, i;
struct BTreeNode *child;
flag = setValue(val, &i, root, &child);
if (flag)
root = createNode(i, child);
}
// 搜索节点
void search(int val, int *pos, struct BTreeNode *myNode) {
if (!myNode) {
return;
}
if (val < myNode->val[1]) {
*pos = 0;
} else {
for (*pos = myNode->count;
(val < myNode->val[*pos] && *pos > 1); (*pos)--)
;
if (val == myNode->val[*pos]) {
printf("%d 找到了", val);
return;
}
}
search(val, pos, myNode->link[*pos]);
return;
}
// 遍历节点
void traversal(struct BTreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->val[i + 1]);
}
traversal(myNode->link[i]);
}
}
int main() {
int val, ch;
insert(8);
insert(9);
insert(10);
insert(11);
insert(15);
insert(16);
insert(17);
insert(18);
insert(20);
insert(23);
traversal(root);
printf("\n");
search(11, &ch, root);
}
// 在 C++ 中搜索 B 树上的键
#include <iostream>
using namespace std;
class TreeNode {
int *keys;
int t;
TreeNode **C;
int n;
bool leaf;
public:
TreeNode(int temp, bool bool_leaf);
void insertNonFull(int k);
void splitChild(int i, TreeNode *y);
void traverse();
TreeNode *search(int k);
friend class BTree;
};
class BTree {
TreeNode *root;
int t;
public:
BTree(int temp) {
root = NULL;
t = temp;
}
void traverse() {
if (root != NULL)
root->traverse();
}
TreeNode *search(int k) {
return (root == NULL) ? NULL : root->search(k);
}
void insert(int k);
};
TreeNode::TreeNode(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
keys = new int[2 * t - 1];
C = new TreeNode *[2 * t];
n = 0;
}
void TreeNode::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
TreeNode *TreeNode::search(int k) {
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
void BTree::insert(int k) {
if (root == NULL) {
root = new TreeNode(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
TreeNode *s = new TreeNode(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
} else
root->insertNonFull(k);
}
}
void TreeNode::insertNonFull(int k) {
int i = n - 1;
if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
void TreeNode::splitChild(int i, TreeNode *y) {
TreeNode *z = new TreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
C[i + 1] = z;
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n = n + 1;
}
int main() {
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);
cout << "B 树为: ";
t.traverse();
int k = 10;
(t.search(k) != NULL) ? cout << endl
<< k << " 找到了"
: cout << endl
<< k << " 没有找到
";
k = 2;
(t.search(k) != NULL) ? cout << endl
<< k << " 找到了"
: cout << endl
<< k << " 没有找到\n";
}
B 树的搜索复杂度
最坏情况时间复杂度：Θ(log n)
平均情况时间复杂度：Θ(log n)
最好情况时间复杂度：Θ(log n)
平均情况空间复杂度：Θ(n)
最坏情况空间复杂度：Θ(n)
B 树的应用
- 数据库和文件系统
- 用于存储数据块（次级存储介质）
- 多级索引