🕌

[超初心者向け！]B+tree 実装をポインタからわかりやすく解説 [C++ Node 構造体編]

2024/06/25に公開

はじめに

B+tree 実装をコーディング初心者でも分かるように解説してみました

この記事の対象者

・B+tree の理論は分かったけど、コードに落とし込めない人
・ポインタがよくわからない人

一緒に実装しましょう！

ポインタ編から勉強したい方はこちら

2. Node の構造体

構造体は、自分で作ることができるオリジナルの型です
B+treeでは以下の型を使います

Node.h

typedef struct _NODE {
   bool isLeaf; //そのノードがleaf nodeであるか否か
   struct _NODE *chi[N]; //子ノードのアドレス
   int key[N-1]; //値
   int nkey; //keyの数
   struct _NODE *parent; //親ノードのアドレス
} NODE;

上から順に、
①そのノードが leaf node であるか否か
②子ノードのアドレス
③値
④key の数
⑤親ノードのアドレス
を表しています

Root Node しかない場合

Root Node しかない場合、
親ノードはなく、子ノードもない状況です
この例だと key には１、２が代入されよってキーの数は２となります

実際の値

Node 構造体

bptree.cpp

#include <iostream>
#include <random>
   
   const int MaxKeyNum = 3;
   
   class Node
   {
   public:
   
       Node *parent;
       Node *children[MaxKeyNum + 1];
       int keys[MaxKeyNum];
       int nkey;
       bool isLeaf;
   };
   
   void print_tree_core(Node *n)
   {
       printf("[");
       for (int i = 0; i < n->nkey; i++)
       {
           if (!n->isLeaf)
               print_tree_core(n->children[i]);
   
           printf("%d", n->keys[i]);
   
           if (i != n->nkey - 1 && n->isLeaf)
               putchar(' ');
       }
   
       if (!n->isLeaf)
           print_tree_core(n->children[n->nkey]);
   
       printf("]");
   }
   
   void print_tree(Node *node)
   {
       print_tree_core(node);
   
       printf("\n");
       fflush(stdout);
   }
   
   Node *root = nullptr;
   
   
   int main()
   {
       root=new Node();
       root->parent = nullptr;
       root->keys[0] = 1;
       root->keys[1] = 2;
       root->nkey=2;
       root->children[0]=nullptr;
       root->children[1]=nullptr;
       root->children[2]=nullptr;
       root->isLeaf = true;
   
       print_tree(root); // check
   
       return 0;
   }

こちらの出力結果は [1 2]
となります

Split が発生する場合

以下の例では Root Node と２つの Leaf Node、合わせて３つの Node があります
Root Node の子ノードアドレスには２つの Leaf Node が、２つの Leaf Node の親ノードアドレスには Root Node のアドレスが紐づけられていることが分かるかと思います

実際の値

Node 構造体

bptree.cpp

#include <iostream>
#include <random>
   
   const int MaxKeyNum = 3;
   
   class Node
   {
   public:
   
       Node *parent;
       Node *children[MaxKeyNum + 1];
       int keys[MaxKeyNum];
       int nkey;
       bool isLeaf;
   };
   
   void print_tree_core(Node *n)
   {
       printf("[");
       for (int i = 0; i < n->nkey; i++)
       {
           if (!n->isLeaf)
               print_tree_core(n->children[i]);
   
           printf("%d", n->keys[i]);
   
           if (i != n->nkey - 1 && n->isLeaf)
               putchar(' ');
       }
   
       if (!n->isLeaf)
           print_tree_core(n->children[n->nkey]);
   
       printf("]");
   }
   
   void print_tree(Node *node)
   {
       print_tree_core(node);
   
       printf("\n");
       fflush(stdout);
   }
   
   Node *root = nullptr;
   Node *left = nullptr;
   Node *right = nullptr;
   
   
   int main()
   {
       root=new Node();
       left=new Node();
       right=new Node();
       
       root->parent = nullptr;
       root->keys[0] = 2;
       root->nkey=1;
       root->children[0]=left;
       root->children[1]=right;
       root->children[2]=nullptr;
       root->isLeaf = false;
       
       left->parent = root;
       left->keys[0] = 1;
       left->nkey=1;
       left->children[0]=nullptr;
       left->children[1]=nullptr;
       left->children[2]=nullptr;
       left->isLeaf = true;
      
       right->parent = root;
       right->keys[0] = 2;
       right->keys[1] = 3;
       right->nkey=2;
       right->children[0]=nullptr;
       right->children[1]=nullptr;
       right->children[2]=nullptr;
       right->isLeaf = true;
   
       print_tree(root); // check
   
       return 0;
   }

こちらの出力結果は [[1]2[2 3]]
となります

最後まで読んでくださりありがとうございました！
次は、コード解説編です！