With the advent of multi-core architectures, it is becoming increasingly important to build scalable data structures that support the basic operations (insert, search) without taking coarse grained locks. Coarse grained locks are usually taken on the entire data structure and prevent any other concurrent thread(s) from operating even on other disjoint/orthogonal parts of the data... Continue Reading →
Use of Associativity in Hashing
In this short post, I will talk about the concept of Associativity in Hashing. This is a fairly well known method so the article might be an old hat for some readers. When implementing a collision resolution strategy for our hash table design, there are usually two directions that we take: Chaining - There is... Continue Reading →
Clustered Indexes v/s Non-Clustered Indexes
In this post, I would like to give a small overview of Clustered and Non-Clustered Indexes. DISCLAIMER: I am an Oracle employee, and the views/opinions expressed in the below article are purely my own and do not express the views of my employer. Let's start with similarities: Similarities: Both Clustered and Non-Clustered indexes are types... Continue Reading →
Primary Index v/s Secondary Index
In this very short post, I will give an overview of primary and secondary indexes in Databases. DISCLAIMER: I am an Oracle employee, and the views/opinions expressed in the below article are purely my own and do not express the views of my employer. Let me tell the similarities first: Similarities Both the index structures... Continue Reading →
Extendible Hashing
In the previous post, I had given a brief description of Linear Hashing technique. In this post, I will talk about Extendible Hashing. Like Linear Hashing, Extendible Hashing is also a dynamic hashing scheme. First let's talk a little bit about static and dynamic hashing as I had skipped this part in my previous post.... Continue Reading →
Linear Hashing
In this blog post, I will give an introduction to a hashing methodology called Linear Hashing. Hash Table Detour A hash table is a well known in-memory structure that supports key-value access with lookup cost being amortized O(1). The hash table is just an array, and each location/index in the array stores a <KEY,VALUE> item.... Continue Reading →
Fenwick Trees
In this post I will talk about Fenwick Trees aka Binary Indexed Trees. I got to use them recently while solving a problem in a coding challenge. Problem: Let's say we have an array of N positive integers. We need to be able to serve the following two operations efficiently: GetPrefixSum(i) - Gets the cumulative... Continue Reading →