B-Tree

B-Treeアルゴリズムを試してみました。

http://github.com/komamitsu/ocaml-b_tree

B-Treeというのは多分木のアルゴリズムで、木の高さを低く保つことができてキーのバランスが良いので、結構DBのインデックスにそれ系統のやつが使われていてDisk I/O減らせてウマー、とのこと。

# 恥ずかしながら、少し前まで二分木のことかと勘違いしていたのは内緒…

使い方は下記のような感じです。複数のkey-valueを登録してから、全keyについてvalueを取り出しています。木の数を変えつつ。

#use "b_tree.ml"

module IntBTree = BTreeMake(struct   
                              type k = int
                              type v = string
                              let compare a b = a - b
                              let debug = fun () -> ()
                            end)

let _ =
  let _test page_size rec_num =
    Random.self_init ();
    let rec _create_page n page cap_keys =
      if n <= 0 then (page, cap_keys)
      else 
        let key = Random.int max_int in
        let value = Printf.sprintf "_%d_" key in
        (*
        let value =
          if n = 500 then Printf.sprintf "_%d_" (key + 1)
          else Printf.sprintf "_%d_" (key + 1) in
        *)
        let new_page = IntBTree.insert page key value in
        _create_page (n - 1) new_page (key::cap_keys)
    in
    let page, cap_keys =
      _create_page rec_num (IntBTree.create_page page_size) [] in
    let rec _assert = function
      | [] -> ()
      | hd::tl ->
          let expected_value = Printf.sprintf "_%d_" hd in
          match IntBTree.find page hd with
          | Some v ->
              assert (expected_value = v);
              _assert tl
          | None -> failwith "not found"
    in
    _assert cap_keys
  in
  _test    2   1000;
  _test   20   1000;
  _test  100  10000

とはいえ、これでは肝心の木の低さが判らないので、上記のテストコードを少し変更して、findで木を降りていく度に文字列を表示させてみる。

module IntBTree = BTreeMake(struct   
                              type k = int
                              type v = string
                              let compare a b = a - b
                              let debug = fun () -> print_endline "hoge"
                            end)
    :
    :
    let key = List.nth cap_keys 5000 in
    let expected_value = Printf.sprintf "_%d_" key in
    match IntBTree.find page key with
    | Some v ->
        assert (expected_value = v)  
    | None -> failwith "not found"   
  in
  _test 80 100000

実行させてみると

komamitsu@garlic:~/git/ocaml-b_tree$ ocaml test_b_tree.ml
hoge
hoge
hoge
komamitsu@garlic:~/git/ocaml-b_tree$

80分木の場合、100000件が深さ3の木に収まっているそうな。どっとわらい。