3
\$\begingroup\$

I have this B-tree based map in Java:

BTreeMap.java

package net.coderodde.util;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

public final class BTreeMap<K extends Comparable<? super K>, V> 
        implements Map<K, V> {

    /**
     * The minimum number of children of a node.
     */
    private static final int MINIMUM_DEGREE = 2;

    /**
     * The minimum number of children of any non-root internal node.
     */
    private static final int DEFAULT_DEGREE = 32;

    /**
     * This class implements the B-tree nodes.
     * 
     * @param <K> the key type. Must be comparable.
     */
    private static final class BTreeNode<K extends Comparable<? super K>> {

        /**
         * The number of key/value pairs in this B-tree node.
         */
        int size;

        /**
         * The array of actual keys of this B-tree node.
         */
        K[] keys;

        /**
         * The array of child nodes of this B-tree node.
         */
        BTreeNode<K>[] children;

        final int minimumDegree;

        BTreeNode(int minimumDegree) {
            this.minimumDegree = minimumDegree;
            this.keys = (K[]) new Comparable[2 * minimumDegree - 1];
        }

        void makeInternal() {
            this.children = new BTreeNode[keys.length + 1];
        }

        boolean isLeaf() {
            return children == null;
        }
    }

    private int modCount;

    /**
     * Maps the keys present in this B-tree to their current values.
     */
    private final Map<K, V> map = new HashMap<>();

    /**
     * The root node of this B-tree.
     */
    private BTreeNode<K> root;

    private final int minimumDegree;

    public BTreeMap(int degree) {
        this.minimumDegree = Math.max(degree, MINIMUM_DEGREE);
        this.root = new BTreeNode(this.minimumDegree);
    }

    public BTreeMap() {
        this(DEFAULT_DEGREE);
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
        return map.containsKey(key);
    }

    @Override
    public boolean containsValue(Object value) {
        throw new UnsupportedOperationException(
                "This BTreeMap does not support containsValue.");
    }

    @Override
    public V get(Object key) {
//        return bTreeSearch(root, (K) key);
        return map.get(key);    
    }

    private V bTreeSearch(BTreeNode<K> x, K key) {
        int i = 0;

        while (i < x.size && key.compareTo(x.keys[i]) > 0) {
            ++i;
        }

        if (i < x.size && key.compareTo(x.keys[i]) == 0) {
            return map.get(key);
        } else if (x.isLeaf()) {
            return null;
        } else {
            return bTreeSearch(x.children[i], key);
        }
    }

    @Override
    public V put(K key, V value) {
        ++modCount;

        if (map.containsKey(key)) {
            return map.put(key, value);
        }

        bTreeInsertKey(key);
        map.put(key, value);
        return null;
    }

    @Override
    public V remove(Object key) {
        if (map.containsKey((K) key)) {
            ++modCount;
            bTreeDeleteKey(root, (K) key);
            return map.remove(key);
        }

        return null;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public void clear() {
        root = new BTreeNode<>(minimumDegree);
        modCount += size();
        map.clear();
    }

    @Override
    public Set<K> keySet() {
        return new KeySet<>();
    }

    @Override
    public Collection<V> values() {
        throw new UnsupportedOperationException(
                "This BTreeMap does not support values.");
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        throw new UnsupportedOperationException(
                "This BTreeMap does not support entrySet.");
    }

    public K getMaximumKey() {
        checkBTreeMapNotEmpty();
        BTreeNode<K> current = root;

        while (!current.isLeaf()) {
            current = current.children[current.size];
        }

        return current.keys[current.size - 1];
    }

    public K getMinimumKey() {
        checkBTreeMapNotEmpty();
        BTreeNode<K> current = root;

        while (!current.isLeaf()) {
            current = current.children[0];
        }

        return current.keys[0];
    }

    public int getMinimumDegree() {
        return minimumDegree;
    }

    private final class KeySet<E> implements Set<E> {

        @Override
        public int size() {
            return map.size();
        }

        @Override
        public boolean isEmpty() {
            return map.isEmpty();
        }

        @Override
        public boolean contains(Object o) {
            return map.containsKey((K) o);
        }

        @Override
        public Iterator<E> iterator() {
            return new KeySetIterator();
        }

        @Override
        public Object[] toArray() {
            throw new UnsupportedOperationException("Not supported yet."); 
        }

        @Override
        public <T> T[] toArray(T[] a) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public boolean add(E e) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public boolean remove(Object o) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public boolean addAll(Collection<? extends E> c) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public boolean removeAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        @Override
        public void clear() {
            throw new UnsupportedOperationException("Not supported yet.");
        }

        private final class KeySetIterator implements Iterator<E> {

            private final int expectedModificationCount = modCount;
            private int globalIterated;
            private int localIterated;
            private final Deque<BTreeNode<K>> nodeStack = new ArrayDeque<>();
            private final Deque<Integer> indexStack = new ArrayDeque<>();

            KeySetIterator() {
                BTreeNode<K> node = root;

                while (node != null) {
                    nodeStack.addLast(node);
                    indexStack.addLast(0);

                    if (node.isLeaf()) {
                        node = null;
                    } else {
                        node = node.children[0];
                    }
                }
            }

            @Override
            public boolean hasNext() {
                checkModificationCount();
                return globalIterated < size();
            }

            @Override
            public E next() {
                checkModificationCount();

                if (!hasNext()) {
                    throw new NoSuchElementException();
                }

                ++globalIterated;

                if (nodeStack.getLast().isLeaf()) {
                    int currentIndex = indexStack.removeLast();
                    BTreeNode<K> currentNode = nodeStack.getLast();
                    E ret = (E) currentNode.keys[currentIndex];

                    if (++currentIndex == currentNode.size) {
                        nodeStack.removeLast();

                        while (!indexStack.isEmpty() && 
                                indexStack.getLast() == 
                                nodeStack.getLast().size) {
                            nodeStack.removeLast();
                            indexStack.removeLast();
                        }
                    } else {
                        indexStack.addLast(currentIndex);
                    }

                    return ret;
                } else {
                    int currentIndex = indexStack.removeLast();
                    E ret = (E) nodeStack.getLast().keys[currentIndex++];
                    indexStack.addLast(currentIndex);
                    nodeStack.addLast(
                            nodeStack.getLast().children[currentIndex]);
                    indexStack.addLast(0);

                    while (!nodeStack.getLast().isLeaf()) {
                        indexStack.addLast(0);
                        nodeStack.addLast(nodeStack.getLast().children[0]);
                    }

                    return ret;
                }
            }

            private void checkModificationCount() {
                if (expectedModificationCount != modCount) {
                    throw new ConcurrentModificationException();
                }
            }
        }
    }

    private void checkBTreeMapNotEmpty() {
        if (map.isEmpty()) {
            throw new NoSuchElementException("This BTreeMap is empty.");
        }
    }

    private void bTreeInsertKey(K key) {
        BTreeNode<K> r = root;

        if (r.size == 2 * minimumDegree - 1) {
            BTreeNode<K> s = new BTreeNode<>(minimumDegree);
            root = s;
            s.makeInternal();
            s.children[0] = r;
            bTreeSplitChild(s, 0);
            bTreeInsertNonFull(s, key);
        } else {
            bTreeInsertNonFull(r, key);
        }
    }

    private void bTreeSplitChild(BTreeNode<K> x, int i) {
        BTreeNode<K> z = new BTreeNode<>(minimumDegree);
        BTreeNode<K> y = x.children[i];

        if (!y.isLeaf()) {
            z.makeInternal();
        }

        z.size = minimumDegree - 1;

        for (int j = 0; j < minimumDegree - 1; ++j) {
            z.keys[j] = y.keys[j + minimumDegree];
            y.keys[j + minimumDegree] = null;
        }

        if (!y.isLeaf()) {
            for (int j = 0; j < minimumDegree; ++j) {
                z.children[j] = y.children[j + minimumDegree];
                y.children[j + minimumDegree] = null;
            }
        }

        int oldSizeOfY = y.size;
        y.size = minimumDegree - 1;
        K pushUpKey = y.keys[minimumDegree - 1];

        for (int j = y.size; j < oldSizeOfY; ++j) {
            y.keys[j] = null;
        }

        for (int j = x.size; j >= i; --j) {
            x.children[j + 1] = x.children[j];
        }

        x.children[i + 1] = z;

        for (int j = x.size - 1; j >= i; --j) {
            x.keys[j + 1] = x.keys[j];
        }

        x.keys[i] = pushUpKey;
        x.size++;
    }

    private void bTreeInsertNonFull(BTreeNode<K> x, K k) {
        int i = x.size - 1;

        if (x.isLeaf()) {
            while (i >= 0 && k.compareTo(x.keys[i]) < 0) {
                x.keys[i + 1] = x.keys[i];
                --i;
            }

            x.keys[i + 1] = k; // ?
            x.size++;
        } else {
            while (i >= 0 && k.compareTo(x.keys[i]) < 0) {
                --i;
            }

            ++i;

            if (x.children[i].size == 2 * minimumDegree - 1) {
                bTreeSplitChild(x, i);

                if (k.compareTo(x.keys[i]) > 0) {
                    i++;
                }
            }

            bTreeInsertNonFull(x.children[i], k);
        }
    }

    private static <K extends Comparable<? super K>> 
        BTreeNode<K> getMinimumNode(BTreeNode<K> x) {
        while (!x.isLeaf()) {
            x = x.children[0];
        }

        return x;
    }

    private static <K extends Comparable<? super K>> 
        BTreeNode<K> getMaximumNode(BTreeNode<K> x) {
        while (!x.isLeaf()) {
            x = x.children[x.size];
        }

        return  x;
    }

    private void bTreeDeleteKey(BTreeNode<K> x, K key) {
        int keyIndex = findKeyIndex(x, key);

        if (keyIndex >= 0) {
            if (x.isLeaf()) {
                // Case 1:
                removeFromLeafNode(x, keyIndex);
                return;
            }

            BTreeNode<K> y = x.children[keyIndex];

            if (y.size >= minimumDegree) {
                // Case 2a:
                BTreeNode<K> tmp = getMaximumNode(y);
                K keyPrime = tmp.keys[tmp.size - 1];
                bTreeDeleteKey(y, keyPrime);
                x.keys[keyIndex] = keyPrime;
                return;
            }

            BTreeNode<K> z = x.children[keyIndex + 1];

            if (z.size >= minimumDegree) {
                // Case 2b:
                BTreeNode<K> tmp = getMinimumNode(z);
                K keyPrime = tmp.keys[0];
                bTreeDeleteKey(z, keyPrime);
                x.keys[keyIndex] = keyPrime;
                return;
            }

            // Case 2c:
            // Merge 'key' and all contents of 'z' to the end of 'y'
            y.keys[y.size] = key;

            for (int i = 0, j = y.size + 1; i != z.size; ++i, ++j) {
                y.keys[j] = z.keys[i];
            }

            if (!y.isLeaf()) {
                for (int i = 0, j = y.size + 1; i != z.size + 1; ++i, ++j) {
                    y.children[j] = z.children[i];
                }
            }

            y.size = 2 * minimumDegree - 1;

            if (!y.isLeaf()) {
                y.children[y.size] = z.children[z.size];
            }

            for (int i = keyIndex + 1; i < x.size; ++i) {
                x.keys[i - 1] = x.keys[i];
                x.children[i] = x.children[i + 1];
            }

            x.children[x.size] = null;
            x.keys[--x.size] = null;
            bTreeDeleteKey(y, key);

            if (x.size == 0) {
                root = y;
            }
        } else { // keyIndex == -1.
            int childIndex = -1;

            for (int i = 0; i < x.size; ++i) {
                if (key.compareTo(x.keys[i]) < 0) {
                    childIndex = i;
                    break;
                }
            }

            if (childIndex == -1) {
                childIndex = x.size;
            }

            BTreeNode<K> targetChild = x.children[childIndex];

            if (targetChild.size == minimumDegree - 1) {
                if (childIndex > 0 
                        && x.children[childIndex - 1].size >= minimumDegree) {
                    // Case 3a: Move from left sibling:
                    if (targetChild.isLeaf()) {
                        BTreeNode<K> leftSibling = x.children[childIndex - 1];

                        K lastLeftSiblingKey = 
                                leftSibling.keys[leftSibling.size - 1];

                        K keyToPushDown = x.keys[childIndex - 1];
                        x.keys[childIndex - 1] = lastLeftSiblingKey;

                        // Shift *all* the stuff in targetChild one step to the 
                        // right:
                        for (int i = targetChild.size - 1; i >= 0; --i) {
                            targetChild.keys[i + 1] = targetChild.keys[i];
                        }

                        targetChild.size++;
                        targetChild.keys[0] = keyToPushDown;
                        leftSibling.keys[--leftSibling.size] = null;
                    } else {
                        BTreeNode<K> leftSibling = x.children[childIndex - 1];

                        K lastLeftSiblingKey = 
                                leftSibling.keys[leftSibling.size - 1];

                        BTreeNode<K> lastLeftSiblingChild = 
                                leftSibling.children[leftSibling.size];

                        K keyToPushDown = x.keys[childIndex - 1];
                        x.keys[childIndex - 1] = lastLeftSiblingKey;

                        // Shift *all* the stuff in targetChild one step to the 
                        // right:
                        targetChild.children[targetChild.size + 1] = 
                                targetChild.children[targetChild.size];

                        for (int i = targetChild.size - 1; i >= 0; --i) {
                            targetChild.keys[i + 1] = targetChild.keys[i];
                            targetChild.children[i + 1] = 
                                    targetChild.children[i];
                        }

                        targetChild.size++;
                        targetChild.keys[0] = keyToPushDown;
                        targetChild.children[0] = lastLeftSiblingChild;
                        leftSibling.children[leftSibling.size] = null;
                        leftSibling.keys[--leftSibling.size] = null;
                    }
                } else if (childIndex < x.size
                        && x.children[childIndex + 1].size >= minimumDegree) {
                    // Case 3a once again, but with the right sibling:
                    if (targetChild.isLeaf()) {
                        BTreeNode<K> rightSibling = x.children[childIndex + 1];

                        K firstRightSiblingKey = rightSibling.keys[0];

                        K keyToPushDown = x.keys[childIndex];
                        x.keys[childIndex] = firstRightSiblingKey;

                        // Shift all the stuff in the right sibling one step to 
                        // the left:
                        for (int i = 1; i < rightSibling.size; ++i) {
                            rightSibling.keys[i - 1] = rightSibling.keys[i];
                        }

                        rightSibling.keys[--rightSibling.size] = null;

                        // Append 'keyToPushDown' to 'targetChild':
                        targetChild.keys[targetChild.size] = keyToPushDown;
                        targetChild.size++;
                    } else {
                        BTreeNode<K> rightSibling = x.children[childIndex + 1];

                        K firstRightSiblingKey = rightSibling.keys[0];
                        BTreeNode<K> firstRightSiblingChild = 
                                rightSibling.children[0];

                        K keyToPushDown = x.keys[childIndex];
                        x.keys[childIndex] = firstRightSiblingKey;

                        // Shift all the stuff in the right sibling one step to 
                        // the left:
                        for (int i = 1; i < rightSibling.size; ++i) {
                            rightSibling.keys[i - 1] = rightSibling.keys[i];
                            rightSibling.children[i - 1] = 
                                    rightSibling.children[i];
                        }

                        // Shit is here! 6.3.2017 klo 14:58
                        rightSibling.children[rightSibling.size - 1] = 
                                rightSibling.children[rightSibling.size];
                        rightSibling.children[rightSibling.size] = null;
                        rightSibling.keys[--rightSibling.size] = null;

                        // Append 'keyToPushDown' to 'targetChild':
                        targetChild.keys[targetChild.size] = keyToPushDown;
                        targetChild.children[++targetChild.size] = 
                                firstRightSiblingChild;
                    }
                } else if (childIndex > 0) {
                    // When we get here, we know that 'targetChild' has left
                    // sibling.
                    BTreeNode<K> leftSibling  = x.children[childIndex - 1];
                    // Case 3b: Merge the left sibling with the target
                    // child:
                    if (targetChild.isLeaf()) {
                        K keyToPushDown = x.keys[childIndex - 1];
                        leftSibling.keys[leftSibling.size] = keyToPushDown;

                        // Merge the contents of 'targetChild' to 
                        // 'leftSibling':
                        for (int i = 0, j = leftSibling.size + 1;
                                i != targetChild.size; ++i, ++j) {
                            leftSibling.keys[j] = targetChild.keys[i];
                        }

                        leftSibling.size = 2 * minimumDegree - 1;

                        // Shit is here
                        // Shift the contents of 'x' after the pushed down 
                        // key one position to the left:
                        for (int i = childIndex; i < x.size; ++i) {
                            x.keys[i - 1] = x.keys[i];
                            x.children[i] = x.children[i + 1];
                        }

                        x.keys[x.size - 1] = null;
                        x.children[x.size] = null;
                        x.size--;

                        if (x.size == 0) {
                            root = leftSibling;
                        }

                        targetChild = leftSibling;
                    } else {
                        K keyToPushDown = x.keys[childIndex - 1];
                        leftSibling.keys[leftSibling.size] = keyToPushDown;

                        // Merge the contents of 'targetChild' to 
                        // 'leftSibling':
                        for (int i = 0, j = leftSibling.size + 1;
                                i != targetChild.size; ++i, ++j) {
                            leftSibling.keys[j] = targetChild.keys[i];
                            leftSibling.children[j] = 
                                    targetChild.children[i];
                        }

                        leftSibling.size = 2 * minimumDegree - 1;
                        leftSibling.children[leftSibling.size] = 
                                targetChild.children[targetChild.size]; // Don't remove! (16:57 6.3.2017)

                        // Shit is somewhere here.
                        // Shift the contents of 'x' after the pushed down 
                        // key one position to the left:
                        for (int i = childIndex; i < x.size; ++i) {
                            x.keys[i - 1] = x.keys[i];
                            x.children[i] = x.children[i + 1];
                        }

                        x.keys[x.size - 1] = null;
                        x.children[x.size--] = null;
//                        x.children[x.size - 1] = x.children[x.size]; // Removed 18:15 (6.3.2017)
//                        x.children[x.size--] = null; // Same as above.

                        if (x.size == 0) {
                            root = leftSibling;
                        }

                        targetChild = leftSibling;
                    }  
                } else {
                    // When we get here, we know that 'targetChild' has right
                    // sibling.
                    BTreeNode<K> rightSibling = x.children[childIndex + 1];

                    // Case 3b (for the right sibling): Merge the right sibling
                    // with the target child:
                    if (targetChild.isLeaf()) {
                        // Append the key from 'x' to the end of 'targetChild':
                        K keyToPushDown = x.keys[childIndex];
                        targetChild.keys[targetChild.size] = keyToPushDown;

                        // Append the contents of 'rightSibling' to the end of
                        // 'targetChild':
                        for (int i = 0, j = targetChild.size + 1; 
                                i != rightSibling.size; 
                                ++i, ++j) {
                            targetChild.keys[j] = rightSibling.keys[i];
                        }

                        targetChild.size = 2 * minimumDegree - 1;

                        // Shift the contents of 'x' after the pushed down key
                        // one position to the left:
                        for (int i = childIndex + 1; i < x.size; ++i) {
                            x.keys[i - 1] = x.keys[i];
                            x.children[i] = x.children[i + 1];
                        }

                        x.children[x.size] = null;
                        x.keys[--x.size] = null;

                        if (x.size == 0) {
                            root = targetChild;
                        }
                    } else {
                        // Append the key from 'x' to the end of 'targetChild':
                        K keyToPushDown = x.keys[childIndex];
                        targetChild.keys[targetChild.size] = keyToPushDown;

                        // Append the contents of 'rightSibling' to the end of
                        // 'targetChild':
                        for (int i = 0, j = targetChild.size + 1; 
                                i != rightSibling.size; 
                                ++i, ++j) {
                            targetChild.keys[j] = rightSibling.keys[i];
                            targetChild.children[j] = rightSibling.children[i];
                        }

                        targetChild.size = 2 * minimumDegree - 1;
                        targetChild.children[targetChild.size] = 
                                rightSibling.children[rightSibling.size];

                        // Shift the contents of 'x' after the pushed down key
                        // one position to the left:
                        for (int i = childIndex + 1; i < x.size; ++i) {
                            x.keys[i - 1] = x.keys[i];
                            x.children[i] = x.children[i + 1];
                        }

                        x.children[x.size - 1] = x.children[x.size];
                        x.children[x.size] = null;
                        x.keys[--x.size] = null;

                        if (x.size == 0) {
                            root = targetChild;
                        }
                    }
                }
            }

            bTreeDeleteKey(targetChild, key);
        }
    }

    private void removeFromLeafNode(BTreeNode<K> x, int removedKeyIndex) {
        for (int i = removedKeyIndex + 1; i < x.size; ++i) {
            x.keys[i - 1] = x.keys[i];
        }

        x.keys[--x.size] = null;
    }

    private static <K extends Comparable<? super K>> 
        int findKeyIndex(BTreeNode<K> x, K key) {
        for (int i = 0; i != x.size; ++i) {
            if (x.keys[i].compareTo(key) == 0) {
                return i;
            }
        }

        return -1;  
    }

    public boolean isHealty() {
        return isHealthy(root);
    }

    private boolean isHealthy(BTreeNode<K> node) {
        if (node.size == 0 && node != root) {
            return false;
        }

        int count = 0;

        for (int i = 0; i < node.keys.length; ++i) {
            if (node.keys[i] == null) {
                break;
            } else {
                count++;
            }
        }

        if (node.size != count) {
            return false;
        }

        if (!node.isLeaf()) {
            count = 0;

            for (int i = 0; i < node.children.length; ++i) {
                if (node.children[i] == null) {
                    break;
                } else {
                    count++;
                }
            }

            if (count != node.size + 1) {
                return false;
            }

            for (int i = 0; i <= node.size; ++i) {
                if (!isHealthy(node.children[i])) {
                    return false;
                }
            }
        }

        return true;
    }
}

Demo.java

import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import java.util.TreeMap;
import net.coderodde.util.BTreeMap;

public class Demo {

    public static void main(String[] args) {
        final int MINIMUM_DEGREE = 16;
        final int UNIVERSE_SIZE = 100_000;
        final int LOAD_SIZE = 1_000_000;
        final int QUERY_SIZE = 1_000_000;
        final int DELETE_SIZE = 500_000;

        Map<Integer, Integer> tree1 = new BTreeMap<>(MINIMUM_DEGREE);
        Map<Integer, Integer> tree2 = new TreeMap<>(); 

        Random random = new Random();

        // Warmup:
        for (int i = 0; i < LOAD_SIZE; ++i) {
            int key = random.nextInt(UNIVERSE_SIZE);
            tree1.put(key, key);
            tree2.put(key, key);
        }

        for (int i = 0; i < QUERY_SIZE; ++i) {
            int key = random.nextInt(UNIVERSE_SIZE);

            if (!Objects.equals(tree1.get(key), tree2.get(key))) {
                throw new IllegalStateException(
                        "Trees do not agree during warmup.");
            }
        }

        for (int i = 0; i < DELETE_SIZE; ++i) {
            int key = random.nextInt(UNIVERSE_SIZE);

            if (!Objects.equals(tree1.remove(key), tree2.remove(key))) {
                throw new IllegalStateException(
                        "Trees do not agree during warmup.");
            }
        }

        if (tree1.size() != tree2.size()) {
            throw new IllegalStateException("Size mismatch after warmup.");
        }

        // Benchmark:
        long seed = System.currentTimeMillis();
        System.out.println("Seed = " + seed);

        Random random1 = new Random(seed);
        Random random2 = new Random(seed);

        long totalTime1 = 0L; 
        long totalTime2 = 0L;

        long startTime = System.currentTimeMillis();

        tree1 = new BTreeMap<>(MINIMUM_DEGREE);

        for (int i = 0; i < LOAD_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree1.put(key, 3 * key);
        }

        long endTime = System.currentTimeMillis();

        System.out.println("BTreeMap.put in " + 
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (Integer i : tree1.keySet()) {

        }

        endTime = System.currentTimeMillis();

        System.out.println("Iteration of BTreeMap in " + 
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < QUERY_SIZE; ++i) {
            int key = random1.nextInt(UNIVERSE_SIZE);
            tree1.get(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("BTreeMap.get in " +
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < DELETE_SIZE; ++i) {
            int key = random1.nextInt(LOAD_SIZE);
            tree1.remove(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("BTreeMap.remove in " +
                (endTime - startTime) + " milliseconds.");

        totalTime1 += endTime - startTime;

        System.out.println("BTreeMap total time: " + totalTime1 +
                " milliseconds.");
        System.out.println();

        ///// TreeMap /////
        startTime = System.currentTimeMillis();

        tree2 = new TreeMap<>();

        for (int i = 0; i < LOAD_SIZE; ++i) {
            int key = random2.nextInt(UNIVERSE_SIZE);
            tree2.put(key, 3 * key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap.put in " + 
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (Integer i : tree2.keySet()) {

        }

        endTime = System.currentTimeMillis();

        System.out.println("Iteration of TreeMap in " + 
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < QUERY_SIZE; ++i) {
            int key = random2.nextInt(UNIVERSE_SIZE);
            tree2.get(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap.get in " +
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        startTime = System.currentTimeMillis();

        for (int i = 0; i < DELETE_SIZE; ++i) {
            int key = random2.nextInt(LOAD_SIZE);
            tree2.remove(key);
        }

        endTime = System.currentTimeMillis();

        System.out.println("TreeMap.remove in " +
                (endTime - startTime) + " milliseconds.");

        totalTime2 += endTime - startTime;

        System.out.println("TreeMap total time: " + totalTime2 +
                " milliseconds.");

        tree1.clear();
        tree2.clear();

        for (int i = 0; i < 100_000; ++i) {
            int key = random1.nextInt();
            tree1.put(key, null);
            tree2.put(key, null);
        }

        Iterator<Integer> iter1 = tree1.keySet().iterator();
        Iterator<Integer> iter2 = tree2.keySet().iterator();

        while (iter1.hasNext()) {
            if (!iter1.next().equals(iter2.next())) {
                throw new IllegalStateException("Iterators disagree!");
            }
        }
    }
}

Performance figures

Seed = 1489690083776
BTreeMap.put in 564 milliseconds.
Iteration of BTreeMap in 60 milliseconds.
BTreeMap.get in 237 milliseconds.
BTreeMap.remove in 129 milliseconds.
BTreeMap total time: 990 milliseconds.

TreeMap.put in 963 milliseconds.
Iteration of TreeMap in 30 milliseconds.
TreeMap.get in 750 milliseconds.
TreeMap.remove in 127 milliseconds.
TreeMap total time: 1870 milliseconds.

As always, any critique is much appreciated.

\$\endgroup\$
  • \$\begingroup\$ I won't guess what you are trying to achieve. Considering java.util.AbstractMap, implementing keySet() in favour of entrySet() surprises me. I left more operations to java.util.Arrays rather than open coded loops. Associating the values via a separate Map is cheeky. The casuistry in bTreeDeleteKey() looks distressingly familiar (had more of that due no proleptic splitting). \$\endgroup\$ – greybeard Mar 20 '17 at 7:14
  • \$\begingroup\$ @greybeard I find entrySet problematic. If a new entry object is created at each key/value pair, I am wasting time. If a same single entry object is used, the client can't save them in another container. \$\endgroup\$ – coderodde Apr 24 '17 at 11:25
1
\$\begingroup\$

It looks like a very nice implementation. The main critique is that this implementation has about twice more overhead owing to the use of an internal HashMap to get fast get performance.

I noticed that put performs very well when it is replacing keys, but that may not be a very realistic workload. When tweaking the parameters a bit (a bigger universe size), the results for put are a lot closer vs TreeMap:

    final int MINIMUM_DEGREE = 16;
    final int UNIVERSE_SIZE = 100_000_000;
    final int LOAD_SIZE = 10_000_000;
    final int QUERY_SIZE = 1_000_000;
    final int DELETE_SIZE = 500_000;

Seed = 1489844488109
BTreeMap.put in 15641 milliseconds.
Iteration of BTreeMap in 526 milliseconds.
BTreeMap.get in 131 milliseconds.
BTreeMap.remove in 142 milliseconds.
BTreeMap total time: 16440 milliseconds.

TreeMap.put in 18767 milliseconds.
Iteration of TreeMap in 660 milliseconds.
TreeMap.get in 1310 milliseconds.
TreeMap.remove in 916 milliseconds.
TreeMap total time: 21653 milliseconds.

I'm also somewhat surprised by the high remove performance. Is your implementation cleaning up after itself properly? Having near empty BTreeNodes would be a big memory waste but avoiding the consolidation of nodes that could be merged could explain the high speed.

This code leads me to believe that remove will leave a lot of empty BTreeNodes lying around:

        if (x.isLeaf()) {
            // Case 1:
            removeFromLeafNode(x, keyIndex);
            return;
        }

The removeFromLeafNode will happily leave an empty node, and there seems to be no further checks to see if the node is empty or empty enough to be consolidated with its next or previous sibling.

\$\endgroup\$
  • \$\begingroup\$ According to my debugging, none unused tree node is left to hang around. Also, the internal HashMap allows me to process puts and removes faster in some situations. \$\endgroup\$ – coderodde Mar 22 '17 at 16:46
  • \$\begingroup\$ I need a HashMap in order to hold the actual key/value mappings. The B-tree is to bring the keys to order. Also, I am not sure how to deal with B-tree deletion algorithm when the requested key is not in the tree. Same for B-tree insertion when the key is already in the tree. \$\endgroup\$ – coderodde Apr 24 '17 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.