Melaksanakan B*-tree dalam C++

B*-Tree: Struktur data yang dioptimumkan untuk mendapatkan semula data yang pantas dalam C++

B* tree ialah struktur data pokok pengimbangan diri yang dioptimumkan untuk mendapatkan data yang pantas. Ia adalah variasi B-tree, struktur data pokok yang direka untuk memastikan data teratur dan seimbang. Ciri pokok B ialah ia sangat teratur, yang bermaksud bahawa nodnya kekal teratur dengan cara tertentu.

B* tree adalah serupa dengan B-tree, tetapi ia dioptimumkan untuk prestasi yang lebih baik. Ini dicapai dengan menggunakan beberapa teknik seperti mampatan laluan dan pemisahan berbilang nod.

B*-pokok amat sesuai untuk sistem fail dan pangkalan data kerana ia menyediakan masa carian dan sisipan yang pantas, menjadikannya cekap apabila menyimpan dan mendapatkan sejumlah besar data. Ia juga sesuai untuk aplikasi yang memerlukan akses data pantas, seperti sistem masa nyata dan simulasi saintifik.

Kelebihan pokok B* berbanding pokok B

Salah satu kelebihan utama B*-trees berbanding B-trees ialah ia mampu memberikan prestasi yang lebih baik kerana penggunaan teknik seperti mampatan laluan dan pemisahan berbilang nod. Teknik ini membantu mengurangkan bilangan akses cakera yang diperlukan untuk mencari dan memasukkan data, menjadikan B*-tree lebih pantas dan lebih cekap daripada B-tree.

Pokok B* juga lebih cekap ruang berbanding pokok B kerana ia mempunyai tahap pesanan yang lebih tinggi dan mampu menyimpan lebih banyak kunci dalam setiap nod. Ini bermakna bahawa lebih sedikit nod diperlukan untuk menyimpan jumlah data yang sama, yang membantu mengurangkan saiz keseluruhan pepohon dan meningkatkan prestasi.

Melaksanakan B*-tree dalam C++

Untuk melaksanakan B*-tree dalam C++, kita mesti mentakrifkan struktur nod terlebih dahulu untuk mewakili setiap nod dalam pokok. Nod B*-tree biasanya mengandungi beberapa kunci dan nilai yang sepadan, serta penunjuk kepada nod anak.

Ini adalah contoh struktur nod yang boleh digunakan untuk melaksanakan pepohon B* dalam C++ -

struct Node {
   int *keys; // Array of keys
   int *values; // Array of values
   Node **children; // Array of child pointers
   int n; // Number of keys in the node
   bool leaf; // Whether the node is a leaf or not
};

Dengan struktur nod yang ditakrifkan, kami kini boleh melaksanakan pokok B* itu sendiri. Berikut ialah contoh cara melaksanakan pepohon B* dalam C++ -

class BTree {
   private:
   Node *root; // Pointer to the root node of the tree
   int t; // Minimum degree of the tree
   public:
   BTree(int _t) {
      root = NULL;
      t = _t;
   }
   // Other member functions go here...
};

Kelas B*-tree di atas mengandungi punca pembolehubah ahli persendirian, yang merupakan penunjuk kepada nod akar pokok dan pembolehubah ahli persendirian t, iaitu darjah minimum pokok itu. Darjah minimum B*-tree ialah bilangan minimum kekunci yang mesti ada pada nod dalam pokok.

Selain pembina, kelas B*tree juga boleh melaksanakan banyak fungsi ahli lain untuk melaksanakan pelbagai operasi pada pokok. Beberapa fungsi ahli yang paling penting termasuk −

• search() − Fungsi ini digunakan untuk mencari kunci tertentu dalam pokok. Mengembalikan penuding ke nod yang mengandungi kunci jika kunci ditemui, atau NULL jika tidak ditemui.

• insert() - Fungsi ini digunakan untuk memasukkan kunci dan nilai baharu ke dalam pokok. Jika pokok itu penuh dan nod akar tidak mempunyai ruang yang mencukupi untuk kunci baharu, nod akar akan berpecah dan akar baharu dicipta.

• split() − Fungsi ini digunakan untuk memisahkan nod lengkap kepada dua nod, dengan kunci dalam nod asal diagihkan sama rata antara dua nod baharu. Kunci median kemudiannya dialihkan ke nod induk.

• delete() - Fungsi ini digunakan untuk memadam kunci tertentu daripada pokok. Jika kekunci tidak ditemui, fungsi ini tidak melakukan apa-apa. Jika kunci ditemui dan nod yang mengandungi kunci tidak penuh, nod boleh digabungkan dengan salah seorang adik-beradiknya untuk memulihkan keseimbangan pada pokok.

Contoh

Berikut ialah contoh pelaksanaan fungsi ahli kelas B*-tree dalam C++:

// Search for a specific key in the tree
Node* BTree::search(int key) {
   // Start at the root
   Node *current = root;
   // Search for the key in the tree
   while (current != NULL) {
      // Check if the key is in the current node
      int i = 0;
      while (i < current->n && key > current->keys[i]) {
         i++;
      }
      // If the key is found, return a pointer to the node
      if (i < current->n && key == current->keys[i]) {
         return current;
      }
      // If the key is not found, move to the appropriate child node
      if (!current->leaf) {
         current = current->children[i];
      } else {
         return NULL;
      }
   }
   // Key was not found in the tree
   return NULL;
}
// Insert a new key and value into the tree
void BTree::insert(int key, int value) {
   // Check if the tree is full
   if (root != NULL && root->n == 2 * t - 1) {
      // Tree is full, so split the root node
      Node *newRoot = new Node(t, true);
      newRoot->children[0] = root;
      root->split(0, newRoot);
      // Determine which child of the new root the key should be inserted into
      int i = 0;
      if (newRoot->keys[0] > key) {
         i++;
      }
      newRoot->children[i]->insertNonFull(key, value);
      root = newRoot;
   } else {
      // Tree is not full, so insert the key into the root node (or a child of the root)
      if (root == NULL) {
         root = new Node(t, true);
      }
      root->insertNonFull(key, value);
   }
}
// Split a full node into two nodes
void Node::split(int index, Node *parent) {
   // Create a new node to hold half of the keys and values from the current node
   Node *newNode = new Node(t, leaf);
   newNode->n = t - 1;
   // Copy the last t - 1 keys and values from the current node to the new node
   for (int i = 0; i < t - 1; i++) {
      newNode->keys[i] = keys[i + t];
      newNode->values[i] = values[i + t];
   }
   // If the current node is not a leaf, copy the last t children to the new node
   if (!leaf) {
      for (int i = 0; i > t; i++) {
         newNode->children[i] = children[i + t];
      }
   }
   // Reduce the number of keys in the current node by t
   n = t - 1;
   // Shift the keys and children in the parent node to make room for the new node
   for (int i = parent->n; i > index; i--) {
      parent->children[i + 1] = parent->children[i];
   }
   // Insert the new node into the parent node
   parent->children[index + 1] = newNode;
   // Move the median key from the current node up to the parent node
   parent->keys[index] = keys[t - 1];
   parent->values[index] = values[t - 1];
   parent->n++;
}
// Insert a new key and value into a non-full node
void Node::insertNonFull(int key, int value) {
   // Determine the position at which the key should be inserted
   int i = n - 1;
   if (leaf) {
      // If the node is a leaf, simply insert the key and value at the appropriate position
      (i >= 0 && keys[i] > key) {
         keys[i + 1] = keys[i];
         values[i + 1] = values[i];
         i--;
      }
      keys[i + 1] = key;
      values[i + 1] = value;
      n++;
   } else {
      // If the node is not a leaf, find the child node into which the key should be
      inserted
      while (i >= 0 && keys[i] > key) {
         i--;
      }
      i++;
      // If the child node is full, split it
      if (children[i]->n == 2 * t - 1) {
         children[i]->split(i, this);
         if (keys[i] < key) {
            i++;
         }
      }
      children[i]->insertNonFull(key, value);
   }
}
// Delete a specific key from the tree
void BTree::deleteKey(int key) {
   // Check if the key exists in the tree
   if (root == NULL) {
      return;
   }
   root->deleteKey(key);
   // If the root node has no keys and is not a leaf, make its only child the new root
   if (root->n == 0 && !root->leaf) {
      Node *oldRoot = root;
      root = root->children[0];
      delete oldRoot;
   }
}

Kesimpulan

Ringkasnya, B*-tree ialah struktur data yang cekap yang sesuai untuk aplikasi yang memerlukan pengambilan data pantas. Mereka mempunyai prestasi dan kecekapan ruang yang lebih baik daripada pokok B, jadi ia sangat popular dalam pangkalan data dan sistem fail. Dengan pelaksanaan yang betul, B*-trees boleh membantu meningkatkan kelajuan dan kecekapan penyimpanan data dan mendapatkan semula dalam aplikasi C++.

Atas ialah kandungan terperinci Melaksanakan B*-tree dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!