• Harkrishn Patro's avatar
    Reduce dbBuckets operation time complexity from O(N) to O(1) (#12697) · 4145d628
    Harkrishn Patro authored
    
    
    As part of #11695 independent dictionaries were introduced per slot.
    Time complexity to discover total no. of buckets across all dictionaries
    increased to O(N) with straightforward implementation of iterating over
    all dictionaries and adding dictBuckets of each.
    
    To optimize the time complexity, we could maintain a global counter at
    db level to keep track of the count of buckets and update it on the start
    and end of rehashing.
    
    ---------
    Co-authored-by: default avatarRoshan Khatri <rvkhatri@amazon.com>
    4145d628
db.c 110 KB