storage: Making use of SkipList-based index

Change-Id: I360af97ae794da383fe00aaad8ab3c417c5167d3
Refs: #1695, #1434
tests: Small refactoring of test cases

Change-Id: I09c372c0c9c8220b3408fafbb41c43e5c216884f
Refs: #1695, #1434