DBMSとB-tree

以下の3つを一致させることが効率性を生む

B-treeにおけるnode

DBMSにおけるpage

Storage (記憶装置) におけるblock

コンピュータに接続される外部記憶装置には、バイトやビットごとにデータの読み書き（アクセス）を行うことができない、あるいはそのようなアクセスでは極端に性能が落ちるものがある。そこで、これらの外部記憶装置ではある程度まとまった固定長のデータ塊ごとにアクセスを行う。この固定長はディスクセクタ、あるいはブロックなどと呼ばれる。 9インチ磁気テープ、フロッピーディスク、ハードディスクドライブ、光ディスク、NAND型フラッシュメモリなどは固定長単位でデータを格納する。 これらの装置を抽象化し同じように扱うため、一部のオペレーティングシステムやデータベース管理システム (DBMS)では、ブロックと呼ぶ固定長のデータ構造体を用意し、ブロック単位で各記憶装置にアクセスを行う。ブロックサイズは一般的に、各記憶装置のアクセス単位よりは大きめに設定される。

データベースはファイルシステム上に構築することもできるが、DBMS が直接ブロック型記憶装置を操作する方が性能がよく、問題発生時のリカバリも容易になる。 DBMSが記憶装置とデータのやり取りを行う最小単位をまた、ブロックあるいはページと呼ぶ。

C言語でB-tree (正確にはB+ tree) を実装することになって理解が捗る

1 blockを4096 bytesとしたときのメモリレイアウトが学べる

参考