Another possible external-memory map implementation is to use a skip list, but t
ID: 3695760 • Letter: A
Question
Another possible external-memory map implementation is to use a skip list, but to collect consecutive groups of O(B) nodes, in individual blocks, on any level in the skip list. In particular, we define an order-d B-skip list to be such a representation of a skip-list structure, where each block contains at least [d/2] list nodes and at most d list nodes. Let us also choose d in this case to be the maximum number of list nodes from a level of a skip list that can fit into one block. Describe how we should modify the skip-list insertion and removal algorithms for a B-skip list so that the expected height of the structure is O(log n/log B).
Explanation / Answer
Insertion in B-skip list:
Consider data,an order-d B-skip list to represent a skip-list structure,where each block contains at leas t[d/2] list nodes and at most d list nodes.
??d?? is the maximum number of list nodes from a level of a skip list that can fit into one block.
A new element ??n?? is inserted in the one list at each level until a singleton list at top level is found.At level 0,new element will be added to the node having a key closest to ??n?? For i>=1 to ??n?? at each level,??n?? will search for the closest element in level i-1 and add to the node to which x belongs.
If a block has more than d elements,split the block and move the largest element to the sibling,make a new block and insert the element in the new block.
In this B-skip list insertion,the expected height of the structure is 0(log n/log B).
Deletion in B-skip list:
To perform remove (key) method,first search for the key in the B-skip list.
Delete the element from each level in bottom-up manner.While deleting an element,check for the block size.
If a block contains at least (d/2) list nodes,simply delete the element form it.
In this B-skip list deletion,the expected height of the structure is o(log n/log B).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.