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

はじめに

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

この記事の対象者

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

一緒に実装しましょう！

目次

1. ポインタ
2. Node構造体
3. コード解説
   コードの書き方はあくまで一例です
   絶対的な解ではありませんので、参考にしていただければ幸いです

１&２ ポインタ / Node 構造体から確認したい人はこちらからどうぞ

https://zenn.dev/risaaa/articles/89585f9b95e99d

https://zenn.dev/risaaa/articles/666d71183d45c5

3. コード解説

流れ1: Rootに値を入れる or Root & Leaf node

まず Leaf Node を探します
ここでは Root が Leaf Node になります

Split の必要がない場合は Root に値を入れます
Split の必要がある場合、Nodeを新たに作成します
→ この場合、Root (値は１つ) と Leaf Node がある状況になります

流れ2: Leaf nodeに値を入れる or Rootを更新

まず Leaf Node を探します
ここでは Root の一個下のノードが Leaf Node になります

Split の必要がない場合は Leaf node に値を入れます
Split の必要がある場合、Nodeを新たに作成します
→ この場合、Root (値は複数) と Leaf Node がある状況になります

流れ3: 中間ノードを作成

まず Leaf Node を探します
ここでは Root の一個以下のノードが Leaf Node になります

Split の必要がない場合は Root に値を入れます
Split の必要がある場合、Nodeを新たに作成します
→ この場合、Root と中間ノードと Leaf Node がある状況になります

これ以上 Split する場合は中間ノードを再帰します

Splitの方法

temp.h

typedef struct _TEMP {
   bool isLeaf;
   NODE *chi[N+1]; // for internal split (for leaf, only N is enough)
   int key[N]; // for leaf split
   int nkey;
} TEMP;

indexについて

Leaf Node の *chiと以下の構造体のアドレスを結びつけます

data.h

typedef struct _DATA {
   int key;
   int val;
   struct _DATA *next;
} DATA;

key には実際の値、struct _DATA *next には右隣の構造体のアドレスを結びつけます
こうすることにより、linked list を作成することができます

最後まで読んでくださりありがとうございました！