Merkel Tree

Step 1: Divide key space into buckets (4 in our example) as shown in Figure 6-13.  A bucket is used as the root level node to maintain a limited depth of the tree.

Step 2: Once the buckets are created, hash each key in a bucket using a uniform hashing method (Figure 6-14).

Step 3: Create a single hash node per bucket (Figure 6-15).

Step 4: Build the tree upwards till root by calculating hashes of children (Figure 6-16).