database - 赤黒木のデメリットとは？

Question

Red - Black ツリーについて読んだすべてのことから、データを格納するのに最適なデータ構造であるように思えます。

私はデータベースを構築しようとしていますが、赤と黒のツリーの実装の面で、どこにもっと注意を払う必要があり、何をすべきでないのか疑問に思っています。

赤と黒は本当に完璧ですか？

Answer 1

データのクエリと更新の方法によって異なります。たとえば、順序付けられたデータが必要ない場合は、ハッシュマップの方が優れている可能性があります。これは、対数ではなく一定時間のルックアップ/挿入が (期待される) ためです。順序付けされたデータが必要な場合でも、赤/黒ツリーは完全ではない可能性があります。特に、ディスクベースのデータベースを実装している場合はそうではありません。ディスクベースの I/O では、シークは順次ブロック読み取りに比べてコストがかかるため、ディスク アクセスの数を最小限に抑えることが目標です。このような場合は、B ツリー (または B+ ツリー、または B* ツリー) の方が適しています。これらはすべて、ディスクに格納したときに高速になるように設計されています。

Answer 2

赤黒木は、すべてのデータ アクセスに最適とは言えません。それらにはそれぞれの場所がありますが、多くの場合、ハッシュ マップや単純な古いリストなどの他の方法の方が適しています。

多くの場合、赤黒ツリーの顕著な欠点の 1 つは、それがバイナリ ツリーであるため、ルックアップが O(lg(n)) であるのに対し、ハッシュ テーブルには O(1) のルックアップがあることです。