[HN Gopher] Indexing semantic versions in RocksDB
       ___________________________________________________________________
        
       Indexing semantic versions in RocksDB
        
       Author : adamretter
       Score  : 23 points
       Date   : 2024-01-03 16:43 UTC (2 days ago)
        
 (HTM) web link (blog.aawadia.dev)
 (TXT) w3m dump (blog.aawadia.dev)
        
       | zokier wrote:
       | I don't know anything about rocksdb, but this approach on surface
       | level seems like it could be very slow? Wouldn't it be more
       | efficient to encode the semver in a format more suitable to
       | sorting
        
         | hdhfjkrkrme wrote:
         | Sure, the old performance/productivity tradeoff.
         | 
         | This quickly solves the problem then you can iterate for
         | performance.
        
       | utopcell wrote:
       | > "The technical primitive data structure here is a hashmap where
       | the keys are sorted."
       | 
       | ..somewhere, this person's algorithms teacher is pondering about
       | his life choices.
        
       | gnulinux wrote:
       | > The technical primitive data structure here is a hashmap where
       | the keys are sorted.
       | 
       | Why not a tree based map instead?
        
         | The_Colonel wrote:
         | HashMap and sorted keys sounds like a contradiction. I think
         | they just use "HashMap" as a generic term for "Map" and it's
         | actually a tree based map.
        
           | morelisp wrote:
           | It is an LSMT, but I cannot imagine why they would need one
           | here.
        
       | samsquire wrote:
       | I am curious, I recently wrote a naive hashmap for C. I am
       | curious about iterating in insert and sort order.
       | 
       | Is it possible for a hash function to maintain a sort
       | relationship to it's input and output?
        
         | hdhfjkrkrme wrote:
         | If you iterate a python dictionary it will return the keys in
         | insert order.
         | 
         | For sort order you need to sort separately.
        
         | blyzz wrote:
         | Supporting insertion order is straightforward (but has some
         | trade-offs) - you store the values in a backing array or linked
         | list, and the hash table array stores pointers to the values.
         | 
         | You could do something similar with a sorted data structure
         | backing the hashmap to get sorted order (a b-tree or something
         | similar).
         | 
         | You could have the hash function preserve order at the cost of
         | it being a very bad hash function. If you had n buckets, then
         | the first 1/n elements in the keyspace would map to bucket 0,
         | then next 1/n elements map to bucket 1, etc.
        
       | morelisp wrote:
       | Using RocksDB here seems fairly insane unless you need to keep
       | (at least) several billion constantly-updating versions sorted.
       | Otherwise you can just use SortedMap and regular Java
       | comparators.
        
       ___________________________________________________________________
       (page generated 2024-01-05 23:01 UTC)