B-koks

Šajā apmācībā jūs uzzināsiet, kas ir B koks. Jūs atradīsit arī B-koka meklēšanas darbības piemērus C, C ++, Java un Python.

B-koks ir īpašs pašbalansējoša meklēšanas koka veids, kurā katrā mezglā var būt vairākas atslēgas un var būt vairāk nekā divi bērni. Tā ir binārā meklēšanas koka vispārināta forma.

Tas ir pazīstams arī kā augstuma līdzsvarots m-way koks.

B-koks

Kāpēc B-koks?

Nepieciešamība pēc B-koka radās, palielinoties vajadzībai pēc mazāka laika piekļuvei fiziskajam datu nesējam kā cietajam diskam. Sekundārās atmiņas ierīces ir lēnākas un ar lielāku jaudu. Bija vajadzīgi šāda veida datu struktūras, kas līdz minimumam samazina piekļuvi diskam.

Citas datu struktūras, piemēram, binārs meklēšanas koks, AVL koks, sarkanmelns koks utt., Vienā mezglā var saglabāt tikai vienu atslēgu. Ja jums ir jāuzglabā liels skaits atslēgu, tad šādu koku augstums kļūst ļoti liels, un piekļuves laiks palielinās.

Tomēr B-koks var saglabāt vairākus taustiņus vienā mezglā, un tam var būt vairāki bērnu mezgli. Tas ievērojami samazina augstumu, ļaujot ātrāk piekļūt diskam.

B-koka īpašības

  1. Katram mezglam x atslēgas tiek saglabātas pieaugošā secībā.
  2. Katrā mezglā ir būla vērtība x.leaf, kas ir taisnība, ja x ir lapa.
  3. Ja n ir koka secība, katrā iekšējā mezglā var būt ne vairāk kā n - 1 atslēgas kopā ar rādītāju katram bērnam.
  4. Katrā mezglā, izņemot sakni, var būt ne vairāk kā n bērni un vismaz n / 2 bērni.
  5. Visām lapām ir vienāds dziļums (ti, koka augstums-h).
  6. Saknei ir vismaz 2 bērni, un tajā ir vismaz 1 atslēga.
  7. Ja n ≧ 1, tad jebkuram n taustiņu B-koku augstumu h un minimālām t ≧ 2, .h ≧ logt (n+1)/2

Operācijas

Meklēšana

Elementa meklēšana B kokā ir vispārināta elementa meklēšanas forma binārā meklēšanas kokā. Tiek izpildītas šādas darbības.

  1. Sākot no saknes mezgla, salīdziniet k ar mezgla pirmo atslēgu.
    Ja k = the first key of the node, atgrieziet mezglu un indeksu.
  2. Ja k.leaf = true, atgrieziet NULL (ti, nav atrasts).
  3. Ja k < the first key of the root node, meklējiet šīs atslēgas kreiso bērnu rekursīvi.
  4. Ja pašreizējā mezglā ir vairākas atslēgas k> the first key, salīdziniet k ar nākamo mezglā.
    Ja k < next key, meklējiet šīs atslēgas kreiso bērnu (ti, k atrodas starp pirmo un otro taustiņu).
    Pārējais, meklējiet pareizo atslēgas bērnu.
  5. Atkārtojiet 1. līdz 4. darbību, līdz lapa ir sasniegta.

Meklēšanas piemērs

  1. Meklēsim taustiņu k = 17kokā zem 3. pakāpes. B-koks
  2. k saknē nav atrodams, salīdziniet to ar saknes atslēgu. k nav atrodams saknes mezglā
  3. Kopš k> 11dodieties pie saknes mezgla labā bērna. Pārejiet uz labo apakškoku
  4. Salīdziniet k ar 16. Kopš k> 16salīdziniet k ar nākamo taustiņu 18. Salīdziniet ar taustiņiem no kreisās uz labo
  5. Tā kā k < 18k atrodas starp 16 un 18, meklējiet labo bērnu no 16 vai kreiso bērnu. K atrodas starp 16 un 18
  6. k ir atrasts. k ir atrasts

Elementa meklēšanas algoritms

 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)

Lai uzzinātu vairāk par dažādām B koka darbībām, lūdzu, apmeklējiet vietni

  • Ievietošana B kokā
  • Dzēšana B kokā

Python, Java un C / C ++ piemēri

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

Sarežģītības meklēšana B kokā

Sliktākajā gadījumā laika sarežģītība: Θ(log n)

Vidējais gadījums Laika sarežģītība: Θ(log n)

Labākais gadījuma sarežģītība: Θ(log n)

Vidējā telpa sarežģītība: Θ(n)

Sliktākais gadījums - kosmiskā sarežģītība: Θ(n)

B koku lietojumi

  • datu bāzes un failu sistēmas
  • uzglabāt datu blokus (sekundāros datu nesējus)
  • daudzlīmeņu indeksēšana

Interesanti raksti...