Table of Contents
Data Structure Approaches
In-memory Processing | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Triple Store Data Structure | In-memory Data Structure | Direct access at loaded position | Direct access URI as ID (pre-loaded) | Iteration foward | Iteration | Append | Append after global last | Insert after loaded item | Insert before loaded item | Insert after loaded position | Insert before loaded position | Delete loaded item | Delete from loaded position | Fetch one by global position | Fetch | Fetch range | Fetch next range | Persist one at global position | Persist one by URI | Persist range | List size | Comments |
doubly linked list | ||||||||||||||||||||||
doubly linked list | NO | SLOW | FAST | FAST | FAST | FAST | FAST | FAST | NO | NO | FAST | NO | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | ||
convert to array on fetch | FAST | SLOW | FAST | FAST | FAST | FAST | FAST | FAST | FAST | FAST | FAST | FAST | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | ||
convert to hash on fetch | NO | FAST | FAST | FAST | FAST | FAST | FAST | FAST | NO | NO | FAST | NO | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | key=proxy URI | |
doubly linked list + order index | ||||||||||||||||||||||
doubly linked list | SLOW | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | FAST | SLOW | SLOW | FAST | SLOW | FAST | ||
convert to array on fetch | FAST | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | FAST | SLOW | SLOW | FAST | SLOW | FAST | ||
convert to hash (key=proxy URI) on fetch | SLOW | FAST | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | FAST | SLOW | SLOW | FAST | SLOW | FAST | key=proxy URI |
Analysis of Triple Store Data Structure
Triple Store Data Structure | Pros | Cons | Comments |
---|---|---|---|
doubly linked list | + all updates effect at most 3 items (prev, current, and next) | - requires traversal of links during fetch (i.e. fetch each item individually - one query for each item) | |
doubly linked list + order index | + much faster fetch retrieving all items in the range with a single query | - adding/removing items from list can be very slow when item is early in the list (worst case touches all list items) |
Analysis of In-memory Data Structure
In-memory Data Structure | Pros | Cons | Comments |
---|---|---|---|
doubly linked list | + least amount of processing during fetch (probably not significant relative to overall processing required) | - iteration requires traversing next links | |
convert to array on fetch | + allows for fast access by position to loaded items | ||
convert to hash on fetch | + allows for fast fast access by proxy URI to loaded items | - iteration requires traversing next links | I anticipate the need to have direct access by proxy URI more than positional. |
List Header Info
Lists with headers will hold the following information.
example value types | Comments | |||||
---|---|---|---|---|---|---|
key | description of value | doubly linked | doubly linked + order | array | hash | |
first | pointer to first item in list | URI of first proxy | URI of first proxy | URI of first proxy | URI of first proxy | |
last | pointer to last item in list | URI of last proxy | URI of last proxy | URI of last proxy | URI of last proxy | |
count | count of all items in list | X | X | X | X | |
first_loaded | pointer to first item in loaded range of items | item | item | array[0] | URI of first loaded proxy | |
current | pointer to current item | item | item | int cpos | URI of current proxy | |
last_loaded | pointer to last item in loaded range of items | item | item | array[size of array] | URI of last loaded proxy | |
count_loaded | count of items in currently loaded range | X | =position of last - position of first | size of array | size of hash | |
resume_token | pointer to item after last_loaded | URI of proxy | URI of proxy | URI of proxy | URI of proxy | |
loaded_items | pointer to loaded items | use first_loaded | use first_loaded | array | hash |
List Item Info
example value types | ||||||
---|---|---|---|---|---|---|
key | description of value | doubly linked | doubly linked + order | array | hash | Comments |
uri | URI of proxy for this item | URI of this proxy | URI of this proxy | URI of this proxy | URI of this proxy | This is the hash key for loaded_items when the list is implemented as a hash. |
prev | pointer to previous item in list | URI of prev proxy | URI of prev proxy | = p - 1 | URI of prev proxy | |
next | pointer to next item in list | URI of next proxy | URI of next proxy | = p + 1 | URI of next proxy | |
prev_loaded | pointer to previous item in loaded range of items | prev item | prev item | = pl - 1 | URI of prev proxy | |
next_loaded | pointer to next item in loaded range of items | next item | next item | = pl + 1 | URI of next proxy | |
proxyFor | URI of list item being aggregated | URI | URI | URI | URI | |
proxyIn | URI of list aggregation | URI of aggregation | URI of aggregation | URI of aggregation | URI of aggregation | |
proxyIn_loaded | pointer to List Header | header | header | header | header | |
position (p) | position in full list | X | p | p | X | |
position_loaded (pl) | position in loaded range of items | X | pl | pl | X |