はじめに
PostgreSQLで使われてるB-Treeについてちょっと調べてみようかと思い、B-Tree関連のREADMEを読んでみたので理解したことの整理。ひとまず全部は理解不可能だった。
B-Treeについて
B-TreeのREADMEはソースファイルの src/backend/access/nbtree/README にあるのでそれを閲覧。
B-Treeの構成はP. Lehman and S. Yaoの論文「Efficient Locking for Concurrent Operations on B-Trees」に基づいているが、deleteに関する箇所はシンプルなロジックにするよう別の論文（V. Lanin and D. Shashaの「A Symmetric Concurrent B-Tree Algorithm」に基づいている。
前者の論文の解説をしているスライドを見つけたのでリンク貼っておく。
https://www.slideshare.net/myui/blinktree-presentation
後者の論文は買わないと入手できないっぽいのでちょっと放置。
論文を読んでみたところ、従来のB-Treeだと、SELECTとINSERTが並行して動いているときにINSERTによってB-TreeがsplitするとSELECT側で問題が発生する可能性があるので、同レベルのページとページを結ぶリンクポインターを用意しましょうというような話だと理解した（超ざっくり）。
アクセスパスの話を考えるときにもconcurrencyの話が出てくるんだなあと感慨深く思ったけど、その界隈の人からするときっと当たり前の話なんだろうなぁ。
PostgreSQLでの変更点
PostgreSQLではLehmanとYaoの論文に完全に則っているわけではなく、いくつか変更点を加えている。
・論文ではB-Treeはすべてユニークキーが前提になっているけど、ユニークキーじゃなくてもB-Treeを使う
・論文ではread lockを必要としていなかったけど、PostgreSQLではread lockをとる
・論文ではリンクポインターを左から右（小さい値から大きい値の方向）に張ることとしていたが、
PostgreSQLでは両方向に張る（インデックスを逆方向からスキャンすることを考慮）
他にもあるみたいだけどとりあえず今日はここまで。
READMEにはこの後にもDeletion Algorithmの解説とかが長々と続くけど、ちょっと理解できなかった。リベンジしたい。