こんにちは。コーポレートエンジニアやってます。橋本 (hassaku (@hassaku_63) | Twitter) です。
2021/07/19（日）に開催された July Tech Festa 2021 （以降、JTF 2021）に登壇してきました。
登壇レポート兼宣伝としてこの記事を書いています。
資料はこちらです。
配信のアーカイブは後日公開とのことなので、気になる方は Fely Tech Festa の Youtube チャンネルをチェックしてみてください。
ちなみに、私の発表は結構喋りで補足している部分が多いので、もし私の発表に興味のある方がいらっしゃるなら動画で見ていただけることをおすすめします。Track C で 13:00 ごろに出演してます。
登壇のモチベ
今回の登壇ネタに関して、私自身は仕事上の接点があるわけではありません。教科書的な知識を仕入れた程度のものです。
そんなのでなぜ登壇に踏み切ったのかというと、今回の JTF 2021 のテーマである「今さら聞けないIT技術」にマッチしてると思ったから、が一番大きいです。
自分自身の理解がふわっとしていて「今さら聞けない」と思っているトピックが今回のネタであり、それを自分でアウトプットしてみればいいじゃない、と。
RDB のインデックスなんてがっつりアプリ開発やってる方なら教養知識だろうなとは思いつつも、多分自分と同じような「わからん仲間」はいらっしゃるんじゃないかとも思ったので応募してみました。あわよくば識者の方が twitter かなにかでツッコミ・補足を入れてくれるかもしれません。そうなれば私にとってもオーディエンスのみなさんにとってもより理解が進んで win-win ですね。
あと、恥ずかしい話私は極めて怠惰な人間でして、強制力のある締め切りを設けないと物事を進められないタチです。なので、勉強を進めるために登壇スケジュールを入れたかった、という狙いもあったりします。
あと、実利的な話として、登壇実績は私個人の名刺代わりになります。技術力の証明にはならなくても、少なくとも「積極的に学ぶ意志があり、それを登壇という形でアウトプットする意識と行動力がある」というメッセージにはなりますよね。そういうメンタルを買ってくれる人たち、あるいは会社さんとお近づきになっておきたい...という思惑もあり、社外登壇の機会には個人的に価値を置いています。
JTF はネタの範囲広めで募集かけてることが多いみたいですし、技術的にも登壇者的にも初心者に門戸が開かれている場所だと思ってます。「社外登壇やってみようかな」って思っている方、デビュー戦にはかなりオススメですよ！まずは Connpass のグループに登録してみましょう。
この発表で言いたかったこと
まあ、ここは「発表見てください」なので詳しくは書きませんが。
「B-Tree とは何か？」を説明する切り口ではなく、「そもそもインデックスがやりたいことは何だったか？」という切り口からスタートしていることが特徴です。
インデックスが実現したいことは「『早く』データにアクセスしたい」ですから、それを達成するためにはどうすればいいか？と紐解いていきます。その流れの先で "B-Tree" というアイデアにたどり着く、そんな流れになっています。B-Tree またはその派生形が具体的にどのようなデータ構造を持っているのか、そうした詳細は扱いません。
技術的な各論・ディテールにいきなり踏み込んでも応用の効かない暗記になってしまうことが多いので、その背景を紐解いていく方が納得感が得られるよねということで今回のようなスタンスになりました。
振り返り
PostgreSQL というワードを使いましたが結果的にタイトル詐欺になってしまいました。懺悔します。
ぶっちゃけ B-Tree 系列のインデックスの話をするだけで 20 分余裕で使い切れるボリュームだったので、これはこれで良かったんだろうとも思いますが。とはいえ当初自分がやりたかったことはできてないので、そこは PostgreSQL アンカンファレンス の登壇ネタとして持ち越しにしようと思います。こっちのコミュニティにも登壇側で参加したいなと思ってるので。
あと、"B-Tree" という用語の使い方について、少々曖昧な表現をしていた点が心残りになりました。B-Tree というデータ構造はいろいろと派生があり、用語の厳密さを詰めるならもうちょっとそのへんに対するスタンスを補足しておくべきでした。
※ wikipedia の解説によれば、リーフノードの持ち方などは文献によって違いがあるようで、実装の詳細にまで立ち入ると定義そのものにもゆらぎがあるようです。このへんの事情は、私は把握できておりません。
なお、PostgreSQL における "B-Tree インデックス" も、大元の "B-Tree" の定義からアレンジしている部分があります。
このことは PostgreSQL のソースコードからも確認することができます。
postgres/src/backend/access/nbtree at REL_10_STABLE · postgres/postgres · GitHub
PostgreSQL 10 系のソースを出典としています。
"The basic Lehman & Yao Algorithm" のアルゴリズムを実装しているようです。
Compared to a classic B-tree, L&Y adds a right-link pointer to each page, to the page's right sibling. It also adds a "high key" to each page, which is an upper bound on the keys that are allowed on that page. These two aadditions make it possible detect a concurrent page split, which allows the tree to be searched without holding any read locks (except to keep a single page from being modified while reading it).
と書かれており、B-Tree の本家大元の定義とは少々データ構造が異なります。
私の発表自体はどうかと言うと、B-Tree の本来の定義に従うものではありませんし、この PostgreSQL における B-Tree インデックスとも異なります。なんと表現すべきかは難しいですが、「厳密な定義に従うものではない」ことと「B-Tree の正確な定義ではなく、アイデアの部分を解説してるよ」と前置きしておくとより明確だったと思います。
...本編では PostgreSQL 要素をほぼ出せなかったので、この場を借りて補足してみました。
さいごに
参加 & 登壇は今回で2回目となりました。次回も何かしら出したいですね。
JTF、みなさんも参加しましょう。視聴者のみなさん、そして運営のみなさんも、ありがとうございました。
