]> git.saurik.com Git - redis.git/blobdiff - doc/SortedSets.html
Fix bug in gluing a deferred multi bulk length to the next reply chunk
[redis.git] / doc / SortedSets.html
index 2a619cf9170976c0026ae5ac90236b2d10e75c08..a9d5f8b358608b22bcbd47f38a329f2cf124c8fe 100644 (file)
@@ -26,8 +26,7 @@
                 </div>
 
                 <div class="narrow">
                 </div>
 
                 <div class="narrow">
-                    &iuml;&raquo;&iquest;#sidebar <a href="SortedSetCommandsSidebar.html">SortedSetCommandsSidebar</a><h1><a name="Redis Sorted Set Type">Redis Sorted Set Type</a></h1>Redis Sorted Sets are, similarly to <a href="Sets.html">Sets</a>, collections of <a href="Stings.html">Redis Strings</a>. The difference is that every member of a Sorted Set hash an <b>associated score</b> that is used in order to take this member in order.<br/><br/>The <a href="ZADD.html">ZaddCommand</a> command is used to add a new member to a Sorted Set, specifying the score of the element. Calling ZADD against a member already present in the sorted set but using a different score will update the score for the element, moving it to the right position in order to preserve ordering.<br/><br/>It's possible to get ranges of elements from Sorted Sets in a very similar way to what happens with <a href="Lists.html">Lists</a> and the <a href="LrangeCommnad.html">LRANGE</a> command  using the Sorted Sets <a href="ZrangeCommand.html">ZRANGE</a> command.<br/><br/>It's also possible to get or remove ranges of elements by score using the <a href="ZrangebyscoreCommand.html">ZRANGEBYSCORE</a> and <a href="ZremrangebyscoreCommand.html">ZREMRANGEBYSCORE</a> commands.<br/><br/>The max number of members in a sorted set is 232-1 (4294967295, more than 4 billion of members per set).<br/><br/>Note that while Sorted Sets are already ordered, it is still possible to use the <a href="SortCommand.html">SORT</a> command against sorted sets to get the elements in a different order.<h1><a name="Implementation details">Implementation details</a></h1>Redis Sets are implemented using a dual-ported data structure containing a skip list and an hash table. When an element is added a map between the element and the score is added to the hash table (so that given the element we get the score in O(1)), and a map between the score and the element is added in the skip list so that elements are taken in order.<br/><br/>Redis uses a special skip list implementation that is doubly linked so that it's possible to traverse the sorted set from tail to head if needed (Check the <a href="ZRevrangeCommand.html">ZREVRANGE</a> command).<br/><br/>When <a href="ZaddCommand.html">ZADD</a> is used in order to update the score of an element, Redis retrieve the score of the element using the hash table, so that it's fast to access the element inside the skip list (that's indexed by score) in order to update the position.<br/><br/>Like it happens for Sets the hash table resizing is a blocking operation performed synchronously so working with huge sorted sets (consisting of many millions of elements) care should be taken when mass-inserting a very big amount of elements in a Set while other clients are querying Redis at high speed.<br/><br/>It is possible that in the near future Redis will switch to skip lists even for the element =&gt; score map, so every Sorted Set will have two skip lists, one indexed by element and one indexed by score.
-
+                    &iuml;&raquo;&iquest;#sidebar <a href="SortedSetCommandsSidebar.html">SortedSetCommandsSidebar</a><h1><a name="Redis Sorted Set Type">Redis Sorted Set Type</a></h1>Redis Sorted Sets are, similarly to <a href="Sets.html">Sets</a>, collections of <a href="Strings.html">Redis Strings</a>. The difference is that every member of a Sorted Set hash an <b>associated score</b> that is used in order to take this member in order.<br/><br/>The <a href="ZaddCommand.html">ZADD</a> command is used to add a new member to a Sorted Set, specifying the score of the element. Calling ZADD against a member already present in the sorted set but using a different score will update the score for the element, moving it to the right position in order to preserve ordering.<br/><br/>It's possible to get ranges of elements from Sorted Sets in a very similar way to what happens with <a href="Lists.html">Lists</a> and the <a href="LrangeCommnad.html">LRANGE</a> command  using the Sorted Sets <a href="ZrangeCommand.html">ZRANGE</a> command.<br/><br/>It's also possible to get or remove ranges of elements by score using the <a href="ZrangebyscoreCommand.html">ZRANGEBYSCORE</a> and <a href="ZremrangebyscoreCommand.html">ZREMRANGEBYSCORE</a> commands.<br/><br/>The max number of members in a sorted set is 232-1 (4294967295, more than 4 billion of members per set).<br/><br/>Note that while Sorted Sets are already ordered, it is still possible to use the <a href="SortCommand.html">SORT</a> command against sorted sets to get the elements in a different order.<h1><a name="Implementation details">Implementation details</a></h1>Redis Sets are implemented using a dual-ported data structure containing a skip list and an hash table. When an element is added a map between the element and the score is added to the hash table (so that given the element we get the score in O(1)), and a map between the score and the element is added in the skip list so that elements are taken in order.<br/><br/>Redis uses a special skip list implementation that is doubly linked so that it's possible to traverse the sorted set from tail to head if needed (Check the <a href="ZRevrangeCommand.html">ZREVRANGE</a> command).<br/><br/>When <a href="ZaddCommand.html">ZADD</a> is used in order to update the score of an element, Redis retrieve the score of the element using the hash table, so that it's fast to access the element inside the skip list (that's indexed by score) in order to update the position.<br/><br/>Like it happens for Sets the hash table resizing is a blocking operation performed synchronously so working with huge sorted sets (consisting of many millions of elements) care should be taken when mass-inserting a very big amount of elements in a Set while other clients are querying Redis at high speed.<br/><br/>It is possible that in the near future Redis will switch to skip lists even for the element =&gt; score map, so every Sorted Set will have two skip lists, one indexed by element and one indexed by score.
                 </div>
         
             </div>
                 </div>
         
             </div>