B- पेड़

इस ट्यूटोरियल में, आप सीखेंगे कि बी-ट्री क्या है। इसके अलावा, आप C, C ++, Java और Python में B- ट्री पर सर्च ऑपरेशन के काम के उदाहरण पाएंगे।

बी-ट्री एक विशेष प्रकार का स्व-संतुलन खोज पेड़ है जिसमें प्रत्येक नोड में एक से अधिक कुंजी हो सकती हैं और दो से अधिक बच्चे हो सकते हैं। यह बाइनरी सर्च ट्री का एक सामान्यीकृत रूप है।

इसे ऊंचाई वाले संतुलित मी-वृक्ष के रूप में भी जाना जाता है।

B- पेड़

क्यों बी-पेड़?

हार्ड डिस्क की तरह भौतिक भंडारण मीडिया तक पहुँचने में कम समय की आवश्यकता के बढ़ने के साथ बी-ट्री की आवश्यकता उत्पन्न हुई। द्वितीयक भंडारण उपकरण एक बड़ी क्षमता के साथ धीमे हैं। इस तरह की डेटा संरचनाओं की आवश्यकता थी जो डिस्क एक्सेस को कम करती हैं।

अन्य डेटा संरचनाएं जैसे कि एक बाइनरी सर्च ट्री, एवल ट्री, रेड-ब्लैक ट्री, आदि एक नोड में केवल एक कुंजी स्टोर कर सकते हैं। यदि आपको बड़ी संख्या में चाबियाँ जमा करनी हैं, तो ऐसे पेड़ों की ऊंचाई बहुत बड़ी हो जाती है और पहुंच का समय बढ़ जाता है।

हालांकि, बी-ट्री एक ही नोड में कई चाबियाँ संग्रहीत कर सकते हैं और कई बच्चे नोड्स हो सकते हैं। यह तेजी से डिस्क एक्सेस की अनुमति देते हुए ऊंचाई को कम करता है।

बी-ट्री गुण

1. प्रत्येक नोड x के लिए, कुंजियाँ बढ़ते क्रम में संग्रहीत की जाती हैं।
2. प्रत्येक नोड में, बूलियन मान x.leaf होता है जो x पत्ती होने पर सत्य होता है।
3. यदि n ट्री का क्रम है, तो प्रत्येक आंतरिक नोड में प्रत्येक बच्चे के लिए एक पॉइंटर के साथ अधिकांश n - 1 कुंजी हो सकती हैं।
4. रूट को छोड़कर प्रत्येक नोड में अधिकांश n बच्चे और कम से कम n / 2 बच्चे हो सकते हैं।
5. सभी पत्तियों की गहराई समान होती है (अर्थात पेड़ की ऊंचाई-एच)।
6. मूल में कम से कम 2 बच्चे हैं और इसमें न्यूनतम 1 कुंजी है।
7. यदि n ≧ 1, तो ऊंचाई एच और न्यूनतम डिग्री के किसी भी एन-कुंजी बी पेड़ के लिए t ≧ 2, ।h ≧ logt (n+1)/2

संचालन

खोज कर

बी-ट्री में एक तत्व की खोज करना बाइनरी सर्च ट्री में एक तत्व की खोज का सामान्यीकृत रूप है। निम्न चरणों का पालन किया जाता है।

1. रूट नोड से शुरू, नोड की पहली कुंजी के साथ तुलना करें।
   यदि k = the first key of the node, नोड और इंडेक्स वापस करते हैं।
2. यदि k.leaf = true, NULL लौटा (यानी नहीं मिला)।
3. यदि k < the first key of the root node, इस कुंजी के बाएँ बच्चे को पुन: खोजा जाए ।
4. यदि वर्तमान नोड में एक से अधिक कुंजी है और k> the first key, नोड में अगली कुंजी के साथ तुलना करें।
   यदि k < next key, इस कुंजी के बाएं बच्चे को खोजें (यानी। k पहली और दूसरी कुंजी के बीच स्थित है)।
   और, कुंजी के सही बच्चे को खोजें।
5. पत्ती तक पहुंचने तक चरण 1 से 4 दोहराएं।

खोज उदाहरण

1. हमें k = 17डिग्री 3. बी-ट्री के नीचे के पेड़ में की खोज करते हैं
2. k रूट में नहीं मिला है, इसलिए इसे रूट की के साथ तुलना करें। k रूट नोड पर नहीं पाया जाता है
3. चूंकि k> 11, रूट नोड के सही बच्चे पर जाएं। सही सबट्री पर जाएं
4. K की तुलना 16 से k> 16करें। चूँकि , k की तुलना अगली कुंजी 18 से होती है। कुंजियों की तुलना बाएँ से दाएँ करें
5. चूंकि k < 18, k 16 और 18 के बीच स्थित है। 16 के दाईं ओर के बच्चे या 18 के बाएं बच्चे में खोजें। k 16 और 18 के बीच स्थित है
6. k पाया जाता है। k पाया जाता है

एक तत्व की खोज के लिए एल्गोरिथ्म

 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) 

विभिन्न बी-ट्री संचालन के बारे में अधिक जानने के लिए, कृपया देखें

• बी-ट्री पर सम्मिलन
• बी-वृक्ष पर विलोपन

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

# 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"; ) 

बी ट्री पर खोज जटिलता

सबसे खराब स्थिति समय जटिलता: Θ(log n)

औसत मामला समय जटिलता: Θ(log n)

सबसे अच्छा मामला समय जटिलता: Θ(log n)

औसत मामला अंतरिक्ष जटिलता: Θ(n)

सबसे खराब स्थिति अंतरिक्ष की जटिलता: Θ(n)

बी ट्री एप्लीकेशन

• डेटाबेस और फ़ाइल सिस्टम
• डेटा के ब्लॉक स्टोर करने के लिए (सेकेंडरी स्टोरेज मीडिया)
• बहुस्तरीय अनुक्रमण