CODEWITHSUNDEEP
databasedata-structuresindexingcomputer-science
Lylia John
Lylia John

Reputation: 61

Adaptive Radix Tree

Since 1 week, I have found one interrested topic called : Adaptive Radix Tree, I found it is very useful techniques used to index memory specially in modern hardware architectures .

Actually I could not understand one point in page 4 , called Node48.

I have attached a picture of what I mean. http://s30.postimg.org/nff1am2r5/xadaptive_radix.png

also this is the main page of the article : http://www-db.in.tum.de/~leis/papers/ART.pdf

So could anybody who is more smart than me to explain that for me, I would be very happy. Thanks.

Upvotes: 2

Views: 1906

Answers (1)

Petrie Wong
Petrie Wong

Reputation: 181

I believe that you understand how NODE_4 and NODE_16 works. In NODE_4 and NODE_16, they put 4 to 16 8-bit keys in the first part of a node. The cost of searching a key are 32 bits and 128 bits that can fit into a regular register and a SIMD register.

However, if we use same way in NODE_48, the cost of searching is read 384 bits that cannot even fit into 256-bit SIMD register. So, Viktor Leis et al. use a child index instead of keys in the first part of NODE_48. The child index contains 256 8-bit offsets that represent the position of a pointer. Eg. If you want to search 103 (it could be 0 to 255) in a NODE_48, the program would:

  1. jump to the 103rd slot in the child index (start from 0th)
  2. read the value from 103rd slot and assume it is 5
  3. jump to the 5th slot in the child pointer
  4. read the pointer value from 5th slot and go to the next node

It does 2 offset calculations instead of 48 (SIMD) selections.

Addition:

For Accessing the 103th element in NODE_4 (or NODE_16):

  1. read the "key" part of the NODE in which there are 4 keys (or 16 in NODE_16) which present the key of the child pointers.
  2. execute a SIMD instruction to compare 103 with all 4 keys.
  3. if one of the keys (let say 3rd key) is 103, follow the 3rd child pointer
  4. if none of the keys is 103, return not found.

Upvotes: 15

Related Questions