Class Art


  • public class Art
    extends java.lang.Object
    See: https://db.in.tum.de/~leis/papers/ART.pdf a cpu cache friendly main memory data structure. At our case, the LeafNode's key is always 48 bit size. The high 48 bit keys here are compared using the byte dictionary comparison.
    • Field Detail

      • root

        private Node root
      • keySize

        private long keySize
      • EMPTY_BYTES

        private static byte[] EMPTY_BYTES
    • Constructor Detail

      • Art

        public Art()
    • Method Detail

      • isEmpty

        public boolean isEmpty()
      • insert

        public void insert​(byte[] key,
                           long containerIdx)
        insert the 48 bit key and the corresponding containerIdx
        Parameters:
        key - the high 48 bit of the long data
        containerIdx - the container index
      • findByKey

        public long findByKey​(byte[] key)
        Parameters:
        key - the high 48 bit of the long data
        Returns:
        the key's corresponding containerIdx
      • findByKey

        private Node findByKey​(Node node,
                               byte[] key,
                               int depth)
      • iterator

        public KeyIterator iterator​(Containers containers)
        a convenient method to traverse the key space in ascending order.
        Parameters:
        containers - input containers
        Returns:
        the key iterator
      • remove

        public long remove​(byte[] key)
        remove the key from the art if it's there.
        Parameters:
        key - the high 48 bit key
        Returns:
        the corresponding containerIdx or -1 indicating not exist
      • removeSpecifyKey

        protected Art.Toolkit removeSpecifyKey​(Node node,
                                               byte[] key,
                                               int dep)
      • leafMatch

        private boolean leafMatch​(LeafNode leafNode,
                                  byte[] key,
                                  int dep)
      • insert

        private Node insert​(Node node,
                            byte[] key,
                            int depth,
                            long containerIdx)
      • commonPrefixLength

        static int commonPrefixLength​(byte[] key1,
                                      int aFromIndex,
                                      int aToIndex,
                                      byte[] key2,
                                      int bFromIndex,
                                      int bToIndex)
      • getRoot

        public Node getRoot()
      • getExtremeLeaf

        private LeafNode getExtremeLeaf​(boolean reverse)
      • serializeArt

        public void serializeArt​(java.io.DataOutput dataOutput)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • deserializeArt

        public void deserializeArt​(java.io.DataInput dataInput)
                            throws java.io.IOException
        Throws:
        java.io.IOException
      • serializeArt

        public void serializeArt​(java.nio.ByteBuffer byteBuffer)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • deserializeArt

        public void deserializeArt​(java.nio.ByteBuffer byteBuffer)
                            throws java.io.IOException
        Throws:
        java.io.IOException
      • serialize

        private void serialize​(Node node,
                               java.io.DataOutput dataOutput)
                        throws java.io.IOException
        Throws:
        java.io.IOException
      • serialize

        private void serialize​(Node node,
                               java.nio.ByteBuffer byteBuffer)
                        throws java.io.IOException
        Throws:
        java.io.IOException
      • deserialize

        private Node deserialize​(java.io.DataInput dataInput)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • deserialize

        private Node deserialize​(java.nio.ByteBuffer byteBuffer)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • serializeSizeInBytes

        public long serializeSizeInBytes()
      • getKeySize

        public long getKeySize()
      • serializeSizeInBytes

        private long serializeSizeInBytes​(Node node)