Cây B

Trong hướng dẫn này, bạn sẽ tìm hiểu B-tree là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ hoạt động về thao tác tìm kiếm trên cây B trong C, C ++, Java và Python.

B-tree là một loại cây tìm kiếm tự cân bằng đặc biệt, trong đó mỗi nút có thể chứa nhiều hơn một khóa và có thể có nhiều hơn hai nút con. Nó là một dạng tổng quát của cây tìm kiếm nhị phân.

Nó còn được gọi là cây chiều cao m cân đối.

Cây B

Tại sao B-tree?

Nhu cầu về B-tree nảy sinh cùng với sự gia tăng nhu cầu ít thời gian hơn trong việc truy cập phương tiện lưu trữ vật lý như đĩa cứng. Các thiết bị lưu trữ thứ cấp chậm hơn với dung lượng lớn hơn. Cần có những kiểu cấu trúc dữ liệu như vậy để giảm thiểu việc truy cập vào đĩa.

Các cấu trúc dữ liệu khác như cây tìm kiếm nhị phân, cây avl, cây đỏ đen, v.v. chỉ có thể lưu trữ một khóa trong một nút. Nếu bạn phải lưu trữ một số lượng lớn chìa khóa, thì chiều cao của những cây như vậy trở nên rất lớn và thời gian truy cập tăng lên.

Tuy nhiên, B-tree có thể lưu trữ nhiều khóa trong một nút duy nhất và có thể có nhiều nút con. Điều này làm giảm chiều cao đáng kể cho phép truy cập đĩa nhanh hơn.

Thuộc tính cây B

  1. Đối với mỗi nút x, các khóa được lưu trữ theo thứ tự tăng dần.
  2. Trong mỗi nút, có một giá trị boolean x.leaf đúng nếu x là một lá.
  3. Nếu n là bậc của cây, mỗi nút bên trong có thể chứa nhiều nhất n - 1 khóa cùng với một con trỏ tới mỗi nút con.
  4. Mỗi nút ngoại trừ gốc có thể có nhiều nhất n con và ít nhất n / 2 con.
  5. Tất cả các lá đều có cùng độ sâu (tức là chiều cao-h của cây).
  6. Gốc có ít nhất 2 con và chứa tối thiểu 1 khoá.
  7. Nếu n ≧ 1, sau đó cho bất kỳ B-cây n-key của chiều cao h và mức độ tối thiểu t ≧ 2, .h ≧ logt (n+1)/2

Hoạt động

Đang tìm kiếm

Tìm kiếm phần tử trong cây B là hình thức tổng quát của việc tìm kiếm phần tử trong Cây tìm kiếm nhị phân. Các bước sau được thực hiện theo.

  1. Bắt đầu từ nút gốc, so sánh k với khóa đầu tiên của nút.
    Nếu k = the first key of the node, trả về nút và chỉ mục.
  2. Nếu k.leaf = true, trả về NULL (tức là không tìm thấy).
  3. Nếu k < the first key of the root node, tìm kiếm đệ quy con bên trái của khóa này.
  4. Nếu có nhiều hơn một khóa trong nút hiện tại và k> the first keyso sánh k với khóa tiếp theo trong nút.
    Nếu k < next key, tìm kiếm con bên trái của phím này (tức là k nằm giữa phím đầu tiên và phím thứ hai).
    Nếu không, hãy tìm kiếm đúng con của khóa.
  5. Lặp lại các bước từ 1 đến 4 cho đến khi đạt được lá.

Tìm kiếm ví dụ

  1. Hãy để chúng tôi tìm kiếm chìa khóa k = 17trong cây bên dưới độ 3. Cây B
  2. k có trong root nên so sánh với root key. k không được tìm thấy trên nút gốc
  3. Kể từ đó k> 11, chuyển đến nút con bên phải của nút gốc. Chuyển đến cây con bên phải
  4. So sánh k với 16. Kể từ đó k> 16, so sánh k với phím tiếp theo 18. So sánh với các phím từ trái sang phải
  5. Vì k < 18, k nằm trong khoảng từ 16 đến 18. Tìm kiếm con bên phải của 16 hoặc con bên trái của 18. k nằm trong khoảng từ 16 đến 18
  6. k được tìm thấy. k được tìm thấy

Thuật toán tìm kiếm phần tử

 BtreeSearch(x, k) i = 1 while i ≦ n(x) and k ≧ keyi(x) // n(x) means number of keys in x node 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)

Để tìm hiểu thêm về các hoạt động B-tree khác nhau, vui lòng truy cập

  • Chèn trên cây B
  • Xóa trên cây B

Ví dụ về Python, Java và C / C ++

Python Java C C ++ 
# Searching a key on a B-tree in Python # Create node 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 # Print the tree 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) # Search key def search_key(self, k, x=None): if x is not None: i = 0 while i x.keys(i)(0): i += 1 if i  = 0 and k(0)  = 0 and k(0)  x.keys(i)(0): i += 1 self.insert_non_full(x.child(i), k) # Split def split(self, x, i): t = self.t y = x.child(i) z = BTreeNode(y.leaf) x.child.insert_key(i + 1, z) x.keys.insert_key(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 main(): B = BTree(3) for i in range(10): B.insert_key((i, 2 * i)) B.print_tree(B.root) if B.search_key(8) is not None: print("Found") else: print("Not found") if __name__ == '__main__': main()   
 // Searching a key on a B-tree in Java public class BTree ( private int T; // Node creation 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; // Search key 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); ) ) // Splitting the node 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 = 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; ) // Inserting a value 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); ) ) // Insert the node final private void insertValue(Node x, int k) ( if (x.leaf) ( int i = 0; for (i = x.n - 1; i>= 0 && k  = 0 && k x.key(i)) ( i++; ) ) insertValue(x.child(i), k); ) ) public void Show() ( Show(root); ) // Display 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)); ) ) ) // Check if present 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("found"); ) else ( System.out.println("not found"); ) ; ) ) 
// Searching a key on a B-tree in C #include #include #define MAX 3 #define MIN 2 struct BTreeNode ( int val(MAX + 1), count; struct BTreeNode *link(MAX + 1); ); struct BTreeNode *root; // Create a node 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; ) // Insert node 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++; ) // Split node 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 val(j - median) = node->val(j); (*newNode)->link(j - median) = node->link(j); j++; ) node->count = median; (*newNode)->count = MAX - median; if (pos val(node->count); (*newNode)->link(0) = node->link(node->count); node->count--; ) // Set the value int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) ( int pos; if (!node) ( *pval = val; *child = NULL; return 1; ) if (val val(1)) ( pos = 0; ) else ( for (pos = node->count; (val val(pos) && pos> 1); pos--) ; if (val == node->val(pos)) ( printf("Duplicates are not permitted"); 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; ) // Insert the value void insert(int val) ( int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); ) // Search node void search(int val, int *pos, struct BTreeNode *myNode) ( if (!myNode) ( return; ) if (val val(1)) ( *pos = 0; ) else ( for (*pos = myNode->count; (val val(*pos) && *pos> 1); (*pos)--) ; if (val == myNode->val(*pos)) ( printf("%d is found", val); return; ) ) search(val, pos, myNode->link(*pos)); return; ) // Traverse then nodes void traversal(struct BTreeNode *myNode) ( int i; if (myNode) ( for (i = 0; i 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(""); search(11, &ch, root); )
// Searching a key on a B-tree in C++ #include 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 traverse(); cout << " " 
 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) 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) 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 keys(j) = y->keys(j + t); if (y->leaf == false) ( for (int j = 0; j 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 << "The B-tree is: "; t.traverse(); int k = 10; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; k = 2; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; )

Tìm kiếm độ phức tạp trên cây B

Trường hợp xấu nhất Độ phức tạp về thời gian: Θ(log n)

Trường hợp trung bình Độ phức tạp về thời gian: Θ(log n)

Trường hợp tốt nhất Độ phức tạp về thời gian: Θ(log n)

Trường hợp trung bình Độ phức tạp không gian: Θ(n)

Trường hợp xấu nhất Độ phức tạp về không gian: Θ(n)

Ứng dụng cây B

  • cơ sở dữ liệu và hệ thống tệp
  • để lưu trữ các khối dữ liệu (phương tiện lưu trữ thứ cấp)
  • lập chỉ mục đa cấp

thú vị bài viết...