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の木に収まっているそうな。どっとわらい。