（技術メモ）B-TREE からノードを削除する
2008年07月31日09:47
先日に引き続き、僕はB-treeというデータベースでとても重要なデータ構造について研究している。 昨日までは追加について研究していたが、今日は削除について検索している。 わかったのだが、削除は追加・検索に比べてはるかに難しい要素があるということがわかった。
これを「リバランシング」と呼ぶ｡
追加は実にシンプルで単純なのだが、削除の方はケース分岐が必要みたいだ。
英語版 wikiに非常に詳細なことが書いてあるのだけど、完璧ではないということも判明してきた。
http://people.ksp.sk/~kuko/bak/index.html
このアプレットはどうやら wiki の説明文を元にして作られたもののようだ。
逐一説明文が出てきて、わかりやすい。
チェコ人が書いたらしい。 素晴らしい。
でも、きちんと原典にあたって調べたい。
B-treeには論文の著者の系列によって、色々な流派があるらしいということがわかってきたからだ。
どこかにきちんと原理が書かれた本があるに違いないと思うのだけど...。
アマゾンで取り寄せるか...。
さて....。
--
追記：
その本とは、クヌースの本だということが判明した。
これは、読むしかないかもしれない...。日本では入手が難しいみたいだ。
訳本は手に入るみたいだけど、訳がまずそうな気がする。 B-treeが Ｂ木とか訳されてると、なんかそれだけで嫌な気分になるな...。
しかし、この書評のおっちゃん、いいことかくなぁ...
http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850
First the basics: it's great, it provides wide-ranging and deep analysis, it shows many views and variants of each problem, and its bibliography is helpful, though not exhaustive. The historical notes, including sorts for drum storage, may seem quaint to modern readers. And sorting has been done, right? You just run a shell program or call a function, and tap into the best technology. Does it need to be done again?
Yes, if you're on the edge of technology, it does need to be done again, and again, and again. That's because technology keeps expanding, and violating old assumptions as it does. Memories got big enough that the million-record sort is now a yawn, where it used to be a journal article. But, at the same time, processor clocks got 100-1000x ahead of memory speeds. All of a sudden, those drum-based algorithms are worth another look, because yesteryear's drum:memory ratios are a lot like today's memory:cache ratios of size and speed - and who doesn't want a 100x speedup? Parallel processing is moving from the supercomputing elite into laptops, causing more tremors in the ground rules. GPU and reconfigurable computing also open whole new realms of pitfalls as well as opportunities.
Knuth points out that the analyses have beauty in themselves, for people with eyes to see it. His analyses also demonstrate techniques applicable way beyond the immediate discussion, too. Today, though, I have nasty problems in technologies that no one really knows how to handle very well. I have to go back and check all the assumptions again, since so many of them changed. If that's the kind of problem you have, too, then this is the place to start.
//wiredweird
追記２：
日本語の本はこっちだ。
http://www.ascii.co.jp/books/books/detail/4-7561-4614-7.shtml
こっちはすぐに入手できるみたいだ。
だけど、翻訳が...。交換ソート、最適ソート、か...。 なんか英語で最初に覚えたので、こうやって訳されると、すごい違和感を覚えるなぁ...。 どれがどれなのか、判別つかないよ...。
これを「リバランシング」と呼ぶ｡
追加は実にシンプルで単純なのだが、削除の方はケース分岐が必要みたいだ。
英語版 wikiに非常に詳細なことが書いてあるのだけど、完璧ではないということも判明してきた。
http://people.ksp.sk/~kuko/bak/index.html
このアプレットはどうやら wiki の説明文を元にして作られたもののようだ。
逐一説明文が出てきて、わかりやすい。
チェコ人が書いたらしい。 素晴らしい。
でも、きちんと原典にあたって調べたい。
B-treeには論文の著者の系列によって、色々な流派があるらしいということがわかってきたからだ。
どこかにきちんと原理が書かれた本があるに違いないと思うのだけど...。
アマゾンで取り寄せるか...。
さて....。
--
追記：
その本とは、クヌースの本だということが判明した。
これは、読むしかないかもしれない...。日本では入手が難しいみたいだ。
訳本は手に入るみたいだけど、訳がまずそうな気がする。 B-treeが Ｂ木とか訳されてると、なんかそれだけで嫌な気分になるな...。
しかし、この書評のおっちゃん、いいことかくなぁ...
http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850
First the basics: it's great, it provides wide-ranging and deep analysis, it shows many views and variants of each problem, and its bibliography is helpful, though not exhaustive. The historical notes, including sorts for drum storage, may seem quaint to modern readers. And sorting has been done, right? You just run a shell program or call a function, and tap into the best technology. Does it need to be done again?
Yes, if you're on the edge of technology, it does need to be done again, and again, and again. That's because technology keeps expanding, and violating old assumptions as it does. Memories got big enough that the million-record sort is now a yawn, where it used to be a journal article. But, at the same time, processor clocks got 100-1000x ahead of memory speeds. All of a sudden, those drum-based algorithms are worth another look, because yesteryear's drum:memory ratios are a lot like today's memory:cache ratios of size and speed - and who doesn't want a 100x speedup? Parallel processing is moving from the supercomputing elite into laptops, causing more tremors in the ground rules. GPU and reconfigurable computing also open whole new realms of pitfalls as well as opportunities.
Knuth points out that the analyses have beauty in themselves, for people with eyes to see it. His analyses also demonstrate techniques applicable way beyond the immediate discussion, too. Today, though, I have nasty problems in technologies that no one really knows how to handle very well. I have to go back and check all the assumptions again, since so many of them changed. If that's the kind of problem you have, too, then this is the place to start.
//wiredweird
追記２：
日本語の本はこっちだ。
http://www.ascii.co.jp/books/books/detail/4-7561-4614-7.shtml
こっちはすぐに入手できるみたいだ。
だけど、翻訳が...。交換ソート、最適ソート、か...。 なんか英語で最初に覚えたので、こうやって訳されると、すごい違和感を覚えるなぁ...。 どれがどれなのか、判別つかないよ...。
コメント一覧
