benchmark BTree vs List

sql_db.ex

defmodule SqlDb do
  @moduledoc """
  # Benchmark of Save and Find

  Name            ips        average  deviation         median         99th %
  btree         50.43       0.0198 s     ±6.77%       0.0197 s       0.0268 s
  list           0.85         1.18 s     ±0.28%         1.17 s         1.18 s

  Comparison:
  btree         50.43
  list           0.85 - 59.29x slower +1.16 s
  """

  defmodule List do
    # list
    def save(db, item) do
      [item | db]
    end

    def find(db, item) do
      Enum.find(db, fn x -> x == item end)
    end
  end

  defmodule BTree do
    ## btree
    def save(db, item) do
      cond do
        is_min_in_this_layer(db, item) ->
          if length(db) < 5 do
            put(db, item)
          else
            [leaf | tail] = db
            [save(leaf, item) | tail]
          end

        true ->
          [leaf, node | tail] = db
          [leaf, node] ++ save(tail, item)
      end
    end

    defp put([], item), do: [[], item, []]
    defp put(db, item), do: [[], item | db]

    # only last leaf
    defp is_min_in_this_layer([_], _), do: true
    defp is_min_in_this_layer([], _), do: true
    defp is_min_in_this_layer([_, node | _], item) when item <= node, do: true
    defp is_min_in_this_layer(_, _), do: false

    def find(db, item) do
      cond do
        match?([_, ^item | _], db) ->
          item

        is_min_in_this_layer(db, item) ->
          case db do
            [] ->
              nil

            [leaf | _] ->
              find(leaf, item)
          end

        true ->
          case db do
            [_, _ | tail] ->
              find(tail, item)

            # last leaf
            [leaf] ->
              find(leaf, item)
          end
      end
    end
  end

  defp test(mod) do
    sample =
      for x <- 1..10000 do
        x
      end
      |> Enum.shuffle()

    db =
      Enum.reduce(sample, [], fn x, acc ->
        mod.save(acc, x)
      end)

    Enum.each(1..10000, fn x ->
      ^x = mod.find(db, x)
    end)

    nil = mod.find(db, -1)
  end

  def run do
    Benchee.run(%{
      "list" => fn -> test(List) end,
      "btree" => fn -> test(BTree) end
    })
  end
end