Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think that if you need to do fast lookups by some key, and modify the results based on actual values, you need two data structures: one for key, one for values.</p> <p>The data structure for key is going to be just an associative array (implement it as a hash-table, self-balancing tree or a skip list, it doesn't matter) from your keys to nodes in a tree for values.</p> <p>The tree for values is going to be a self-balancing binary search tree (or a skip-list, see edit below). The nodes in the tree have a delta associated with them, along with their value. The delta applies to all nodes that are greater than or equal to particular node, i.e. it applies to itself and to all nodes in its right subtree.</p> <p>When you insert a value, you increment the delta of all nodes bigger than or equal to the value that you are inserting. This increments the actual value of all nodes whose value is bigger than or equal to the value you are inserting in the whole tree. Deletion is similar, you just with increment replaced with decrement.</p> <p>When you want to read a value, you use the key-based structure to find the node in the value-based tree. You then climb to the root (you have to keep pointers to parents of nodes in the tree for this) and accumulate delta from nodes, whose value is greater than or equal to the value in the node where you started.</p> <p>You have to be careful when doing rebalancing as the self-balancing algorithm you chose requires, because you have to recalculate the deltas of some of the nodes, but this shouldn't affect the time complexity.</p> <p><strong>EDIT:</strong> For skip-list, managing the deltas is quite easy: when you are looking for a place to insert, increment delta in every node in the linked list you compare to that is greater than or equal that the value you are inserting (which also means that you are going one level down). Deletion is similar, except that you have to move any deltas the deleted item held to the right.</p> <p>When you want to compute actual value of a certain node, climb as high as you can in the current item, apply the delta there (one item can have deltas from one insertion or deletion multiple times on different levels, you always have to use the value in the highest level), then go in the linked list one node to the left and repeat the process until you reach the leftmost item.</p> <p>The way you are accessing the nodes also means the linked lists have to be doubly-linked.</p>
    singulars
    1. This table or related slice is empty.
    1. POIncrementing values in a search tree after insertion of a key-value pair
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USsvick
    1. USsvick
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POIncrementing values in a search tree after insertion of a key-value pair
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHow would you modify to support a skip-list instead of the balanced binary tree (since it seems that the balance algorithm would need to be complex to handle the delta management)?
      singulars
      1. PO
      1. USjsherer
    2. COI would have to think about that (maybe tomorrow I will). But it should be fairly easy to do in a [scapegoat tree](http://en.wikipedia.org/wiki/Scapegoat_tree): just evaluate the actual values and reset any deltas in the subtree that you are currently rebuilding.
      singulars
      1. PO
      1. USsvick
    3. CO@jordan, see edit.
      singulars
      1. PO
      1. USsvick
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload