修行の場

知人が言っていました。これは修行だと。

B TreeとML

背景

MongoDBやMySQLではインデックスとしてBツリーが使われています。 インデックスが表形式のデータの高速アクセスの要なので、 大量データを扱う上でMongoDBやMySQLの制約を知る上で理解しておく必要があります。

B treeの基本とアプリケーション

Bツリーの平均計算量と最悪計算量は

  • insert: O(logn)
  • delete, update: O(logn)
  • search: O(logn)

です。オーダー上はRed-Black Treeと同様になりますが、 B Treeはディスクやストレージに格納されてアクセスされる場合にRed Black Treeよりも性能が優位になります。 その理由は今のストレージシステムはある単位でデータを読み出すことで最も性能が引き出せるので、その性質を親和性が高いからです。 例えば、Amazon EBSでは最大IOPSはSSDでは、16KB読み出した場合、HDDの場合は1MB読み出した場合の性能になり、その単位で読み出すことで最大性能が出せます。

B TreeはRed-Black Treeなどの2分探索木とは次の2点で異なります。

  • 子は2つ以上でも良い
  • 一つのノードは複数のキーを持つ

なので、一つのノードのサイズを高速に読める読み出し単位例えばSSDなら、16KBにすることでディスクアクセス回数がかなり減ります。 Red-Black Treeなら、O(logn)で対数の底は2、B Treeは底が約16000になります。 B Treeは読み出し単位に合わせたツリーと言えるでしょう。

ディスクの選択

例えば、AmazonのEBSの中でB Treeインデックスに適したものはEBS Provisioned IOPS SSDです。 このSSDであれば1兆レコードあるインデックスであったとしても、3ブロック読み込めば良いだけなので、約20マイクロ秒でディスクから読み込め、それメモリ上でプラス16000レコードからの二分探索をすれば良いだけでかなり高速にデータをとれます。1兆レコードで整数IDなら数十TBのデータになるので容量的には厳しいかもしれませんが...

とにかく、速度のこと飲みを考えるのであれば、SSDになるでしょう。

基本的な操作

(省略)

まとめ

今後、MLの適用範囲が増えていくに従い、実験にML環境を自前で構築するといった用途も増えてくると思います。その場合に、Bツリーを知っておくことでどういったケースでMySQLやMongoDBが使えて、どういったケースで他の方法を頼らなければならないか想像がつく手助けになると思います。