Package org.roaringbitmap.art
Class Art
java.lang.Object
org.roaringbitmap.art.Art
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.
-
Nested Class Summary
Nested Classes -
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static int
commonPrefixLength
(byte[] key1, int aFromIndex, int aToIndex, byte[] key2, int bFromIndex, int bToIndex) private Node
deserialize
(DataInput dataInput) private Node
deserialize
(ByteBuffer byteBuffer) void
deserializeArt
(DataInput dataInput) void
deserializeArt
(ByteBuffer byteBuffer) long
findByKey
(byte[] key) private Node
first()
private LeafNode
getExtremeLeaf
(boolean reverse) long
getRoot()
void
insert
(byte[] key, long containerIdx) insert the 48 bit key and the corresponding containerIdxprivate Node
boolean
isEmpty()
iterator
(Containers containers) a convenient method to traverse the key space in ascending order.last()
private boolean
leafNodeIterator
(boolean reverse, Containers containers) leafNodeIteratorFrom
(long bound, boolean reverse, Containers containers) long
remove
(byte[] key) remove the key from the art if it's there.protected Art.Toolkit
removeSpecifyKey
(Node node, byte[] key, int dep) private void
serialize
(Node node, DataOutput dataOutput) private void
serialize
(Node node, ByteBuffer byteBuffer) void
serializeArt
(DataOutput dataOutput) void
serializeArt
(ByteBuffer byteBuffer) long
private long
serializeSizeInBytes
(Node node)
-
Field Details
-
root
-
keySize
private long keySize -
EMPTY_BYTES
private static byte[] EMPTY_BYTES
-
-
Constructor Details
-
Art
public Art()
-
-
Method Details
-
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 datacontainerIdx
- 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
-
iterator
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
-
leafMatch
-
insert
-
commonPrefixLength
static int commonPrefixLength(byte[] key1, int aFromIndex, int aToIndex, byte[] key2, int bFromIndex, int bToIndex) -
getRoot
-
getExtremeLeaf
-
first
-
last
-
serializeArt
- Throws:
IOException
-
deserializeArt
- Throws:
IOException
-
serializeArt
- Throws:
IOException
-
deserializeArt
- Throws:
IOException
-
leafNodeIterator
-
leafNodeIteratorFrom
-
serialize
- Throws:
IOException
-
serialize
- Throws:
IOException
-
deserialize
- Throws:
IOException
-
deserialize
- Throws:
IOException
-
serializeSizeInBytes
public long serializeSizeInBytes() -
getKeySize
public long getKeySize() -
serializeSizeInBytes
-