Forem: Andrés Barón Sandoval.

Finding strongly connected components (SCC) in directed graphs: Kosaraju-Sharir vs Tarjan’s algorithm in Go

Andrés Barón Sandoval. — Wed, 22 Mar 2023 15:32:57 +0000

Graphs are non-linear data structures in which a problem is represented as a network by connecting nodes and edges, examples of this can be networks of communication, flows of computation, paths in a road, connections in social networks, etc. The next image shows graph connections of Facebook for the year 2010:

Figure 1. Population centers in bright white (from the density of intra-city friendships). [1]

This image shows interesting information such as, which countries the app has more or less influence, you can also see cultural relations between countries: Hawaii to the continental US; Australia to New Zealand; Colombia to Spain, you could also observe country outlines like India isolated in the dark void of China and Russia[1].

In short, Graph algorithms offer the tools required to understand, model, and establish connection behaviors of systems at a high level of complexity.

This article will discuss the theory behind the most popular algorithms to find strongly connected components (SCC), the time complexity of each and finally compare both algorithms using benchmarks on directed graphs. Let's start defining what directed graphs are:

Directed Graphs

A directed graph (also known as Digraph) is a type of graph in which the edges have a defined direction (Figure 2), unlike an undirected graph, in which the edges are symmetrical relations and do not point in any direction, the edges are bidirectional (Figure 3).

Figure 2. Representation of a directed graph.

Figure 3 . Representation of an undirected graph.

A graph is connected if there is a path between every pair of vertices, in digraphs there are two classifications depending on the nature of the connections, weakly connected and strongly connected. A digraph is called weakly connected, if it is possible to reach any node starting from any other node by traversing edges in some direction not necessarily in the direction they point [3].

Figure 4. Illustration of a weakly connected digraph.

On the other hand, a digraph is called strong connected, if for each pair of vertices u and v, there is a path from u to v and a path from v to u, in other words, if there is a path in each direction between each pair of vertices of the graph.

Figure 5. Connection between U-V and V-U.

To find this strong connected components, DFS (Depth first search) can be used, the two most famous algorithms that use this traversal technique are:

Kosaraju-Sharir algorithm
Tarjan’s algorithm

Kosaraju-Sharir algorithm

In the year 1978, computer scientist S.Rao Kosaraju proposed an implementation of the algorithm but did not publish it. Independently, computer scientist Micha Sharir discovered it and published it in 1981. The main idea of the algorithm is based on the fact that the strongly connected components of a graph A are exactly the same as those of the transposed graph of A (reversing all the edges of graph A).

Algorithm steps:

1. Create a graph
For the creation of the graph an adjacency list will be used, an adjacency list consists in a collection of unordered lists (child nodes) grouped by a map, where each key represents the parent node. The code shown below handles an implementation of the graph with a struct having the following fields:

nodes: this field has the purpose of keeping track of all labels associated to vertices in the graph.
reversed: As said before, Kosaraju-Sharir algorithm makes use of the transposed graph, to save unnecessary iterations like traversing the graph to find the transposed, simply when adding a new edge to the base graph, also add the same edges in reversed direction (See section 2, line 10).
edges: Adjacency list of the graph.

package kosarajuSharir

import (
    g "SCC_analysis/graph"
    "fmt"
    "github.com/abaron10/Gothon/gothonSlice"
)

type graph struct {
    nodes    []int
    reversed *graph
    edges    map[int][]*edge
}

type edge struct {
    from int
    to   int
}

func newEdge(from int, to int) *edge {
    return &edge{from: from, to: to}
}

func NewGraph() g.Graph {
    reversedGraph := &graph{nodes: []int{}, edges: map[int][]*edge{}}
    return &graph{nodes: []int{}, edges: map[int][]*edge{}, reversed: reversedGraph}
}

Section 1. Graph implementation.

To add some nodes and edges to the graph, define a method like the following:

func (g *graph) AddEdge(from int, to int) {
    edges, _ := g.edges[from]
    edges = append(edges, newEdge(from, to))

    g.edges[from] = edges
    g.nodes = append(g.nodes, from)

    //Computing transposed graph at the same time user adds an Edge.
    if g.reversed != nil {
        g.reversed.AddEdge(to, from)
    }
}

Section 2. AddEdge method, required to populate base and reversed graph.

Section 1. Graph implementation
3. Topological Sort with DFS traversal

Topological sort is a linear ordering of vertices such that for every directed edge u-v, vertex u comes before v in the ordering [4]. Create an empty stack, do DFS, and after finishing all recursive calls for all adjacent vertices of a node, append the visiting node to stack.

func (g *graph) calculateStackBaseOrder() []int {
    visited := map[int]struct{}{}
    stack := []int{}

    for _, node := range g.nodes {
        if _, ok := visited[node]; !ok {
            g.dfs(node, visited, &stack)
        }
    }

    return stack
}

Section 3. Topological sort on base graph.

Depending on where DFS starts, and the order in which nodes are visited, the stack will be populated, don't forget to visit all the nodes in the graph, hence the importance of the slice nodes (remember this attribute of the struct, has the purpose of keeping track of all added labels in the graph).

The iteration on g.nodes (See section 3, line 5) will go one by one comparing against the visited set, if there is an unvisited node, the code pass it through the DFS implementation.


func (g *graph) dfs(from int, visited map[int]struct{}, stack *[]int) {
    visited[from] = struct{}{}
    edges, ok := g.edges[from]
    if ok {
        for _, edge := range edges {
            if _, ok = visited[edge.to]; !ok {
                g.dfs(edge.to, visited, stack)
            }
        }
    }
    *stack = append(*stack, from)
}

Section 4. DFS implementation to traverse base graph and populate the stack.

4. Reverse Graph

While adding new edges with the method addEdge, the reversed graph was also getting populated with the reversed edges, that means, that at least with this implementation, the reversed graph has already been computed.

5. Second DFS traversal on reversed graph following topological sort found on step 3.

At this step, the algorithm already computed the topSort order on the base graph, now traverse the reversed graph in that order. To do this, first define a second DFS traversal function and pop nodes from orderNodes, while orderNodes is not empty (To pop the slice an handle it like a stack, the code is using Gothon's library), take the popped node and call the reversed DFS implementation, see that a counter and a map called _scc _are being passed to the method, in order to tag the strongly connected components.

func (g *graph) findSCCComponents(orderNodes []int) map[int]int {
    visited := map[int]struct{}{}
    scc := map[int]int{}
    counter := 0

    for len(orderNodes) > 0 {
        //using https://github.com/abaron10/Gothon library to emulate stack popping as Python do
        node := gothonSlice.Pop(&orderNodes, -1)
        if _, ok := visited[node]; !ok {
            g.dfsReversed(node, visited, scc, counter)
            counter++
        }
    }

    return scc
}

Section 5. Computing strong connected components popping the order from the stack.

Similarly as the previous topological sort, after calling recursive DFS for all adjacent edges of a node, the node label is saved as a key in the map with the respective SCC identifier (given by the counter).

func (g *graph) dfsReversed(from int, visited map[int]struct{}, scc map[int]int, counter int) {
    visited[from] = struct{}{}
    scc[from] = counter
    edges, ok := g.reversed.edges[from]
    if ok {
        for _, edge := range edges {
            if _, ok = visited[edge.to]; !ok {
                g.dfsReversed(edge.to, visited, scc, counter)
            }
        }
    }
    scc[from] = counter
}

Section 6. DFS implementation to traverse transposed graph and populate the SCC map.

After computing both traversals on the map scc , there can be found keys corresponding to node labels and the values corresponding to the SCC identifier.

Time complexity:

Kosaraju's algorithm performs Depth First Search on the directed graph twice. Since the implementation is using an adjacency list, each vertex is processed with all the neighboring edges, as a result of this, time complexity is:

Where V corresponds to the vertices and E the edges within a graph.

Tarjan’s algorithm

Invented by Robert Tarjan in 1972, the structure of the algorithm is based on the fact that the strongly connected components, together, form subtrees whose roots are the strongly connected components.

Algorithm steps:

1. Create implementation
The implementation of the graph is similar to the explained previously for Kosaraju's algorithm using and adjacency list, the difference lies on the addition of the following fields to the struct:

stack: Keeps track of the nodes visited while forming a subtree of the graph.
onStack: Keeps track of the nodes in the stack, avoiding iterating over the slice to check if a node exists or not.
id: Incremental identifier of a node within a formed subtree.
ids: This field use a map whose function is to translate node label to current incremental id within the graph.
lowLink: Tarjan’s algorithm maintains a low-link number, which is initially assigned the same value as the id number when a vertex is visited the first time.

package tarjan

import (
    g "SCC_analysis/graph"
    "fmt"
    "github.com/abaron10/Gothon/gothonSlice"
)

type graph struct {
    nodes   []int
    onStack map[int]struct{}
    stack   []int
    ids     map[int]int
    id      int
    lowLink map[int]int
    edges   map[int][]*edge
}

type edge struct {
    from int
    to   int
}

func newEdge(from int, to int) *edge {
    return &edge{from: from, to: to}
}

func NewGraph() g.Graph {
    return &graph{nodes: []int{}, ids: map[int]int{}, lowLink: map[int]int{}, edges: map[int][]*edge{}, onStack: map[int]struct{}{}, stack: []int{}, id: -1}
}

Section 7. Graph declaration to implement Tarjan's algorithm.

2. Depth First Search (DFS) traversal tagging nodes with an incremental id

Start DFS on any node (On figure 6, DFS is started at node 0), when visiting assign an id and a low link to the current node, both with the same value. Append visited nodes to the stack.

Figure 6. Example of tagging low links and ids for nodes starting DFS on 0.

See that on figure 6, the next node to visit from node 2 is 0, but 0 is already in the visited stack, if this happens, calculate the minimum low-link value between the current node and the node in the stack.

If the value of the node in the visiting stack is smaller, a strong connected component has been found.

5. Propagate low link value if found SCC

After calling recursive DFS for all adjacent edges of a node, if the current visiting node created a strong connected component, pop nodes off stack until reaching the node that started the recursive DFS. While doing this, update the new low link value of each popped node.

The advantage of this, is the propagation of low link values throw graph cycles.

func (g *graph) dfs(from int, graph map[int][]*edge, visited map[int]struct{}) {
    visited[from] = struct{}{}
    g.id++
    g.ids[from] = g.id
    g.lowLink[from] = g.id

    g.onStack[from] = struct{}{}
    g.stack = append(g.stack, from)

    edges, ok := graph[from]
    if ok {
        for _, edge := range edges {
            if _, ok = visited[edge.to]; !ok {
                g.dfs(edge.to, graph, visited)
            }

            if _, ok = g.onStack[edge.to]; ok {
                g.lowLink[from] = Min(g.lowLink[from], g.lowLink[edge.to])
            }
        }
    }

    if g.ids[from] == g.lowLink[from] {

        for true {
            node := gothonSlice.Pop(&g.stack, -1)
            delete(g.onStack, node)
            g.lowLink[node] = g.ids[from]

            if node == from {
                break
            }
        }
    }
}

Section 8. DFS implementation to find SCCs with Tarjan's algorithm.

Time complexity:
Since computing SCC's doing DFS traversal on the graph, the time complexity is the same as Kosaraju's obtaining an overall of:

Where V corresponds to the vertices and E to the edges within a graph.

Algorithm's evaluation

To test both algorithm's, Digraph on figure 7 will be used. See that there is a path in each direction between pairs of vertices on each connected component.

Figure 7. Example of Digraph (Directed graph) with 5 SCCs.

To understand the response of each algorithm, the method computeAnswer offers a more readable approach by arranging the computed SCC map into a text answer.


func (g *graph) computeAnswer(sccKeys map[int]int) {
    response := map[int][]int{}
    for node, sscComponent := range sccKeys {
        response[sscComponent] = append(response[sscComponent], node)
    }

    fmt.Println("The SCC (Strongly connected components) calculated with Kosaraju's Algorithm are:")
    for _, value := range response {
        fmt.Printf("- %v \n", value)
    }
}

Section 9. Method used to get a readable response of computed SCC components.

Kosaraju’s Algorithm

After recreating graph shown on figure 7 and evaluating Kosaraju’s algorithm, the following response can be expected:

func (g *graph) EvaluateSCC() {
    baseOrder := g.calculateStackBaseOrder()
    sccResult := g.findSCCComponents(baseOrder)
    g.computeAnswer(sccResult)
}

Section 10. Kosaraju's algorithm executed.

Figure 8. Computed answer of SCC using Kosaraju's algorithm

Tarjan’s Algorithm
The same computing as above, but with Tarjan’s Algorithm give the following response:

func (g *graph) EvaluateSCC() {
    visited := map[int]struct{}{}

    for _, node := range g.nodes {
        if _, ok := visited[node]; !ok {
            g.dfs(node, g.edges, visited)
        }
    }
    g.computeAnswer(g.lowLink)
}

Section 11. Tarjan’s algorithm executed.

Figure 9. Computed answer of SCC using Tarjan’s algorithm

Benchmark on both solutions

On the next code snippet, the reader can observe the benchmark used to compare both implementations on graph shown on figure 7, the purpose of this, is to check which algorithm is more efficient to find SCC's than the other.

func BenchmarkSCCs(b *testing.B) {

    edges := map[int][]int{0: {1, 5}, 3: {5, 2, 3}, 2: {0, 3},
        5: {4}, 4: {3, 2}, 6: {4, 0, 8, 9}, 8: {6, 7},
        7: {6, 9}, 11: {4, 12}, 9: {11, 10}, 10: {12},
        12: {9}}

    b.Run("SCC with Tarjan's Algorithm", func(b *testing.B) {
        tarjanImplementation := tarjan.NewGraph()
        graph.PopulateGraph(tarjanImplementation, edges)

        for i := 0; i < b.N; i++ {
            tarjanImplementation.EvaluateSCC()

        }
    })
    b.Run("SCC with Kosaraju's Algorithm", func(b *testing.B) {
        kosarajuImplementation := kosarajuSharir.NewGraph()
        graph.PopulateGraph(kosarajuImplementation, edges)

        for i := 0; i < b.N; i++ {
            kosarajuImplementation.EvaluateSCC()
        }
    })
}

Section 12. Benchmark with both algorithms testing graph on figure 7.

Figure 10. Benchmark of both algorithms.

On figure 10, on the right side of the function name, for SCC_with_Tarjan’s_Algorithm the SCC calculation was executed 585250 times with an average of 2057 ns/op (nanoseconds per operation), while SCC_with_Kosaraju’s_Algorithm was executed 512942 times with an average of 2220 ns/op. On this test, Tarjan’s algorithm is faster finding SCCs with an advantage of 163 ns/op over kosaraju’s algorithm. This can be explained understanding the basic approach of the two algorithms, Kosaraju’s algorithm performs DFS twice, unlike Tarjan’s algorithm where the graph is only traversed through DFS once.

Both algorithms have linear time complexity but as evidenced by the benchmark, Tarjan’s algorithm has a more efficient handling of operations per unit of time and a better control of constant factors saving additional DFS navigations.

Memory allocation statistics
In terms of allocated space, the benchmark test is using 24329.65 MB in total for both approaches, but notice on figure 11 that around 82.65% (20108.60 MB) of the memory goes to Kosaraju's algorithm, the other 17.29% (4207.57 MB) was allocated by Tarjan's.

Figure 11. PPROF on both algorithms to check allocated memory.

It can be affirmed looking at figure 12 that Kosaraju’s algorithm uses more memory than Tarjan’s algorithm, partly due to a greater number of recursive calls when traversing the base graph (allocating memory on the stack) and also having the pointer in memory of the transposed graph at running time.

Figure 11. PPROF on both algorithms to check allocated memory.

To avoid keeping the pointer of the transposed graph in memory, a valid option can be, reversing the original graph at running time, but once the calculations with the transposed graph are finished, the graph must be reversed again in order to achieve the original configuration. With this approach, the graph must be traversed at least twice, doubling the constant execution times.

Conclusions

Both algorithms perform similarly in general execution time O(V), however Tarjan's approach is more efficient with constant factors of time and memory at execution. In software, everything is a tradeoff, but due to performance challenges, in highly complex distributed systems, any gain in time, even in units of nano seconds, is a significant gain. Under this premise, Tarjan's algorithm is a much more attractive option.
Tarjan’s algorithm has more development complexity than Kosaraju’s, however both algorithms serve as tools to better understand graph theory and its applicability to the world of technology.

Code implementation

https://github.com/abaron10/Kosaraju_vs_Tarjan

References

https://blog.revolutionanalytics.com/2010/12/facebooks-social-network-graph.html
Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009). 3.https://mathworld.wolfram.com/WeaklyConnectedDigraph.html#:~:text=A%20weakly%20connected%20digraph%20is,indegree%20of%20at%20least%201.
https://www.geeksforgeeks.org/topological-sorting/

Optimizing Database Performance: Exploring Indexing Techniques in DBMS

Andrés Barón Sandoval. — Thu, 16 Mar 2023 01:25:25 +0000

In today's data-driven world, databases play a crucial role in modern computing, serving as the backbone of countless applications and systems. A critical component of database management is indexing, which helps optimize database performance by speeding up data retrieval. In this article, we will explore indexing techniques in SQL and their impact on query performance.

Indexing is a powerful tool in the database world, used to speed up search and retrieval of data. By creating a data structure that maps the values in a column to the location of the corresponding rows, indexing can dramatically reduce the amount of time needed to perform certain queries. However, not all indexing techniques are created equal, and different techniques are better suited for different types of data and queries. In this article, we'll explore some of the most common indexing techniques used in computer science and discuss their strengths and weaknesses, providing you with a solid foundation for optimizing the performance of your own databases.

The Theory Behind Indexing

In a traditional database, data is stored in tables that are composed of rows and columns. When a query is performed on a database, the database engine must search through every row in the table to find the data that matches the query conditions. This process can be time-consuming, especially when the table is very large, or the query conditions are complex.

Indexing works by creating a separate data structure that maps the values in a particular column to the location of the corresponding rows in the table. By creating an index on a column, the database engine can quickly locate the rows that match a particular value or range of values in that column, without having to search through every row in the table.

Before understanding the main techniques of indexing, it's important to have a basic understanding of how a hard drive works.

Hard drives
Hard drives are physical devices that store data on magnetic disks. Each disk is segmented in a particular way in order to save data, these sections are:

A block is the smallest unit of data that can be read from or written to a hard drive. Blocks are typically 512 bytes in size, although this can vary depending on the hard drive and the operating system.
A sector is a subdivision of a track on a hard drive. Tracks are concentric circles on the surface of the disk, and sectors are pie-shaped sections of each track. Each sector typically contains one or more blocks of data, along with some additional information such as an error correction code.
A track is a circular path on the surface of the hard drive that contains multiple sectors. The number of tracks on a hard drive varies depending on the size of the disk and the density of the data stored on it. Modern hard drives can have thousands of tracks per inch, allowing for very high data densities.

Figure.1 - Illustration of how hard drives are organized.

When data is read from or written to a hard drive, the disk rotates at high speeds, typically several thousand revolutions per minute, and the read/write head moves across the surface of the disk to access the desired track and sector. As the read/write head can only access one track at a time, data is read and written in blocks that are spread out across multiple sectors on the same track. However, searching for data row by row can become time-consuming. To reduce this time and avoid inefficient resource consumption, indexing techniques come into play.

Non-Clustered Index

A non-clustered index is a type of database index that creates a separate data structure to map the values of the indexed column(s) to the physical locations of the data on disk. When a non-clustered index is created, the database engine generates a new data structure that stores a copy of the indexed column(s), along with a pointer to the location of the corresponding data row(s) in the table. Unlike a clustered index, a non-clustered index arranges the data logically rather than physically. Therefore, the physical order of rows may differ from that of columns in a non-clustered index. As a result, the index is constructed to logically order the data based on the columns of the index.

Figure.2 - Non-clustered index representation showing how order differs from the original organization.

When a query is executed that involves the indexed column(s), the database engine can use the non-clustered index to quickly locate the relevant rows in the table, without having to perform a full table scan. The engine follows the pointers in the index to locate the data rows on disk, and then retrieves the relevant data from those rows.

Advantages:

More flexibility: Non-clustered indexes allow for greater flexibility in database design, as they can be created on any column in a table, including those that do not have a primary key.
Improved concurrency: Non-clustered indexes can improve database concurrency by reducing the need for table locks during data retrieval operations.
Reduced disk usage: Non-clustered indexes typically require less disk space than clustered indexes, as they only store a copy of the indexed column(s) and the corresponding pointer(s) to the actual data.

Disadvantages:

Additional maintenance overhead: Non-clustered indexes require regular maintenance to ensure that they remain effective, which can add to the administrative burden of managing a database.
Potential for fragmentation: Over time, non-clustered indexes can become fragmented, which can reduce their effectiveness and slow down data retrieval operations.
Reduced query performance for some queries: While non-clustered indexes can speed up data retrieval for some queries, they can actually slow down performance for others, particularly those that involve multiple joins or complex search criteria.

Clustered Index

When a clustered index is created, the database engine creates a new data structure that stores a copy of the indexed column(s), along with a pointer to the physical location of the corresponding data row(s) in the table. However, instead of creating a separate data structure, the engine rearranges the data rows in the table so that they are physically stored in the order specified by the index key.

Figure.3 - Clustered index representation, used to physically order the data on disk

Advantages

No additional disk space requirement: Clustered indexes physically store data on disk in a sorted order, which makes it faster to retrieve data because the database engine can seek directly to the data without having to perform additional sorting operations.
Reduced disk I/O: Clustered indexes can reduce disk I/O by storing all related data in a single location, which makes retrieving data faster and easier.
Simplified maintenance: Clustered indexes typically require less maintenance compared to non-clustered indexes because they are directly linked to the table and don't require additional indexing.

Disadvantages

Increased write time: Clustered indexes can slow down write operations, as the entire table must be reorganized when a new row is inserted, updated, or deleted from the table.
Limited flexibility: Clustered indexes can only be created on one column per table and are usually based on the primary key.
Difficulty with range searches: If a query involves a range search (i.e., a search for values within a specific range), a clustered index may not be the best option because it can be slow to traverse the entire index to find matching values.

B-tree indexes

In a B-tree index, the index is stored as a tree, with each node representing a range of values from the indexed column. The root node represents the entire range of values in the indexed column, while the leaf nodes represent individual values.

Figure.4 - General B-tree model representation.[1]

To understand this, please consider the table shown in Figure 5, where each row can store 128 bytes of data, and one block on the hard drive can store four rows of that table.

Figure.5 - Citizen table with 1000 rows, including columns for citizen_name and favorite_color. The sizes of each column per row are shown on the right, this values are examples meant for representation purposes only, and do not necessarily reflect the actual size values stored in disk.

To find a record with an ID of 1000, we would need to search through 250 blocks on the disk (Since one block can hold 512 Bytes). However, we can improve performance by adding an index structure (as shown in Figure 6), to store a pointer for each ID. This enables quick access to the exact location of a given input on the disk, improving the speed of record retrieval.

Indexes are also stored on disk, and the space required to store an ID (10 bytes) and a pointer (6 bytes) gives a total of 16 bytes for each row in the index structure. As a result, up to 32 ID entries can be stored per disk block.

Figure.6 - Representation of disk memory management for the citizens table.

Now, if a user needs to retrieve record 3, the index pointer for ID = 3 can be used to quickly locate the specific block on the disk that contains that record. This allows the database system to access the desired record much more quickly and efficiently than if it had to search through all of the blocks on the disk. However, there is still room to further improve performance. As a reminder, 32 ID entries are equivalent to 512 Bytes. Another layer can be added to map each 32 Byte block, which would further improve performance.

For example, when searching for ID=32, the database system can start at the first layer (Indexes block) and determine that the desired record is located in the first block. Then, the system can move to the second layer (Indexes-Table) to obtain the exact pointer where the data is stored.

Figure.7 - Representation of disk memory management with multi-level indexing.

Figure 7 provides a good representation of the concept of multilevel indexing, a technique commonly used in database management systems. With multilevel indexing, the index is itself indexed, creating a hierarchical structure of indexes that enables efficient searching and retrieval of data.

When Figure 7 is rotated by 90 degrees and with some added creativity, a tree structure similar to the one in Figure 8 becomes visible.

Figure.8 - B-tree branching representation for first block.

B-trees are a type of multilevel indexing in which data is stored in a hierarchical structure of nodes, with each node containing a certain number of keys and pointers to child nodes. The use of B-trees in database management systems is a prime example of how multilevel indexing techniques can be employed to optimize database performance.

Advantages:

Efficient access: B-trees provide efficient access to data, even in very large databases. The hierarchical structure allows for rapid access to data, making B-trees well-suited for applications with high read-to-write ratios.
Scalability: B-trees are designed to scale well as the size of the database grows. By adding new nodes to the tree as needed, B-trees can handle very large datasets without significant performance degradation.
Flexibility: B-trees are flexible and can be used to index many different types of data, including numerical, alphabetical, and even non-sequential data.
Range queries: B-trees are particularly effective at performing range queries, which involve searching for data that falls within a specific range of values. This is because the hierarchical structure of the tree allows for rapid traversal of data that meets certain criteria.
Self-balancing: B-trees are designed to self-balance as new data is added, deleted, or modified. This means that performance remains consistent even as the database changes over time.

Disadvantages:

Overhead: B-trees require additional storage space to maintain the index, which can be significant in large databases.
Complexity: The implementation of B-trees can be complex, and the algorithms used to maintain the index can be difficult to optimize.
Write-intensive operations: B-trees are optimized for read operations and can be slower for write-intensive operations, such as inserting or deleting records from the database.
Limited flexibility: B-trees are well-suited for certain types of data, such as numerical or alphabetical data, but may not perform as well with more complex or unstructured data.
Fragmentation: As data is added, deleted, or modified, B-trees can become fragmented, which can negatively impact performance over time. Regular maintenance is required to prevent or mitigate fragmentation.

Bitmap Index

Unlike traditional indexes, which create a list of pointers to the locations of the indexed data, bitmap indexes store a bitmap for each unique value in the indexed column. Each digit corresponds to a specific value in the indexed column, and if a digit is 1, it indicates that the corresponding value is present in the data, while a digit of 0 means that the value is absent.To understand this please consider the following table:

Figure.9 - Citizen table with new added rows showing its cardinality.

In Figure.9, cardinality refers to the number of distinct values in a column. For example, the column ID has a cardinality of 1000 since every ID on the table is unique, and the same is true for the name column assuming each name does not repeat in another row. On the other hand, the Gender and is_active columns both have a cardinality of 3 and 2, respectively. When a bitmap index is created on the Gender column, the database system generates three bitmaps. These bitmaps include one for "Female", another for "Male", and finally one for "Non-Binary". Each of these bitmaps contains a sequence of 1s and 0s that indicate which rows contain that value.

Figure.10 - Bitmap index on the gender column.

A bitmap index can quickly determine which rows contain a specific value or set of values by storing a bitmap for each unique value in the indexed column, without having to search through the entire table.

Advantages:

Faster querying: Bitmap indexing can significantly speed up queries that involve filtering or grouping by values in the indexed columns. Since bitmaps are small and easy to manipulate, the database can quickly retrieve the relevant rows without having to scan the entire table.
Reduced I/O: Because bitmap indexes store only binary values (0 or 1) for each row, they require much less disk space than other types of indexes. This can lead to reduced I/O and better performance overall.
Simple to implement: Bitmap indexing is a simple technique that can be easily implemented in most database management systems. It can be used with any data type and is especially effective for low-cardinality columns.
Concurrent access: Bitmap indexes can be easily updated and maintained while the database is still in use. This means that other users can still access and modify the database while the index is being updated.

Disadvantages:

High memory usage: Bitmap indexes can consume a significant amount of memory, especially for high-cardinality columns. This can lead to increased memory requirements for the database and may require additional hardware resources.
Slow inserts: Bitmap indexes are not well-suited for tables that require frequent inserts or updates. Updating a bitmap index can be time-consuming and may require the entire index to be rebuilt, which can slow down database performance.
Limited applicability: Bitmap indexing is most effective for low-cardinality columns, and may not be as useful for columns with high cardinality or columns that require complex queries.
Complexity for range queries: Bitmap indexes are not well-suited for range queries (e.g., finding all values greater than a certain threshold), as these queries require the use of multiple bitmaps and may be slow to execute.

Hashing Indexing

Hash indexing is a technique used to locate data records quickly based on a key value. This technique works by using a hash function to generate a fixed-length key value, which is used to find data records in the database.

The hash function is a mathematical function that takes an input value (known as the key) and produces a fixed-length output (known as the hash code). The hash code is used as an index into a hash table that contains pointers to the data records. The hash table is typically stored in memory to enable fast access.

Figure.11 - Representation of Hashing indexing on each row of the table.

However, hash indexing has some limitations. One limitation is that it can be challenging to design a good hash function that provides a uniform distribution of hash codes. If the hash function is poorly designed, it can lead to collisions, where two or more keys produce the same hash code. This can slow down the search process, as the DBMS has to search through the hash table to find the correct data record.

Advantages:

Fast access to data records: Hash indexing can provide fast access to data records, as long as the hash function is well-designed and the hash table is appropriately sized.
Efficient for exact matches: Hash indexing is well-suited for exact match queries, where the search criteria is an exact match to the key value.
Small storage space: Compared to other indexing techniques like B-trees, hash indexing requires relatively small storage space in memory.
Good for large datasets: Hash indexing can be especially efficient for large datasets where exact match queries are common.

Disadvantages:

Limited flexibility: Hash indexing is not well-suited for range queries, where the search criteria is a range of values.
Poorly designed hash functions can lead to collisions: If the hash function is poorly designed, it can lead to collisions, where two or more keys produce the same hash code. This can slow down the search process.
Additional overhead: Hash indexing requires additional overhead to maintain the hash table, which can increase the cost of storage and retrieval.
Limited support for complex data types: Hash indexing is limited in its support for complex data types like text and binary data, which may require additional processing to generate a hash code.

Full text Indexing

This indexes are used to improve the performance of full-text search queries in a database. Full-text search allows users to search for words or phrases within the text of documents, web pages, or other unstructured data stored in the database.

Traditional indexes, like B-tree indexes, are optimized for searching for exact values, such as an integer or a string. However, they are not well-suited for full-text search, which involves searching for words or phrases within blocks of text.

It works by breaking down the text into words, known as "tokens," and creating an index of those tokens. This index allows the database engine to quickly search for documents or records that contain specific words or phrases.

Advantages

Improved search performance: Full-text indexes allow for more efficient searching of large amounts of text data, resulting in faster and more accurate search results.
Flexible search capabilities: Full-text search allows for more flexible search capabilities, including searching for words or phrases within the text, as well as the ability to perform more complex searches using Boolean operators and other search parameters.
Better support for natural language search: Full-text indexes are designed to support natural language search, which means that they can understand and interpret natural language queries in a more human-like way.
Better handling of misspellings and synonyms: Full-text indexes can be configured to handle common misspellings and synonyms, which can help to improve the accuracy of search results.

Disadvantages

Increased storage requirements: Full-text indexes can require significant amounts of storage space, especially for large text data sets.
Higher processing overhead: Full-text indexes can be more resource-intensive to create and maintain than other types of indexes, which can lead to higher processing overhead and slower query performance.
Limited support for structured data: Full-text indexes are designed to work with unstructured text data, which means that they may not be well-suited for searching structured data or data that is stored in a highly normalized format.
Limited support for some languages: Full-text indexes may not support all languages equally well, and some languages may require additional configuration or customization to work effectively with full-text search.

Indexing techniques supported by DB engines

MySQL: supports B-tree indexes, hash indexes, and full-text indexes.
PostgreSQL: supports B-tree indexes, hash indexes, GiST (Generalized Search Tree) indexes, SP-GiST (Space-Partitioned Generalized Search Tree) indexes, GIN (Generalized Inverted Index) indexes, and BRIN (Block Range Index) indexes.
Oracle: supports B-tree indexes, bitmap indexes, hash clusters, and function-based indexes.
Microsoft SQL Server: supports clustered indexes (B-tree), nonclustered indexes (B-tree), full-text indexes, and XML indexes.
MongoDB: supports B-tree indexes, hash indexes, and geospatial indexes.
Cassandra: supports B-tree indexes and secondary indexes (global and local).
SQLite: supports B-tree indexes and full-text search using FTS (Full-Text Search) extension.

It's worth noting that each database engine may have different variations of these indexing techniques, and some may support additional indexing methods not listed here.

Benchmark

To further investigate the indexing techniques discussed in the previous paragraphs, a performance test was conducted to compare a query that searches for a citizen's name in two different scenarios: one without an index and the other with a B-tree index.

Set up
To set up the test, a script was executed to insert 12,000 citizen records into a Postgres database. The objective of the test was to search these 12,000 rows for the citizen named "Laura Donaldson" using the "citizen_name" column, assuming that names in this column are unique.

Figure.12 - Citizen table after the registers insertion.

To measure the performance of each scenario, a benchmark in Python was implemented to execute 100 iterations of the query. This allowed for precise measurement of the execution time of the query. A sample of the benchmark code is provided below.

import psycopg2
import timeit

# Connect to the database
conn = psycopg2.connect(host="localhost", database="citizen", user="postgres", password="postgres")
cur = conn.cursor()

# Define the query to be benchmarked
query = "SELECT * FROM citizen WHERE citizen_name = 'Laura Donaldson'"

# Define the number of iterations and the setup code
number = 100
setup = """
import psycopg2
conn = psycopg2.connect(host="localhost", database="citizen", user="postgres", password="postgres")
cur = conn.cursor()
"""
# Define the function to be timed
def benchmark_query():
    cur.execute(query)

# Run the benchmark and print the results
time = timeit.timeit(benchmark_query, setup=setup, number=number)
print("Average execution time: {:.2f} ms".format(time * 1000 / number))

For scenario 2 (using a B-tree index), the following SQL command was executed in the database in order to create an index:

CREATE INDEX btree_citizen_name ON citizen USING BTREE (citizen_name)

Results
After executing the performance tests for the first scenario (without the index) for 100 iterations, the following result was obtained:

Average execution time: 0.95 ms

For the second scenario (using a B-tree index), the following result was obtained:

Average execution time: 0.11 ms

As evident from the results, there was a significant difference of approximately 0.84 between the two scenarios. This indicates that using indexing provides a much greater advantage than executing queries without indexing. The performance boost provided by indexing can be attributed to the efficient organization and retrieval of data using the index, which reduces the number of disk accesses and leads to faster query execution times. Overall, the use of indexing is a highly effective strategy for improving the performance of database queries.

Conclusion

Selecting the appropriate indexing technique is crucial for database performance optimization. Each indexing technique has its own strengths and weaknesses, and selecting the right one depends on the specific needs of the database system.
Ultimately, choosing the right indexing technique is a balancing act between the system's performance requirements, storage capacity, and the type of queries that the system will handle. Therefore, careful consideration of the database design, including the indexing technique used, is essential for achieving optimal performance in any database system.

References

[1] CIS Department > Tutorials > software design using C++ > B-trees. Available at: https://cis.stvincent.edu/html/tutorials/swd/btree/btree.html (Accessed: March 14, 2023).

[2] MikeRayMSFT Indexes - SQL server, SQL Server | Microsoft Learn. Available at: https://learn.microsoft.com/en-us/sql/relational-databases/indexes/indexes?view=sql-server-ver16 (Accessed: March 15, 2023).

[3] Blogs.oracle.com. Available at: https://blogs.oracle.com/sql/post/how-to-create-and-use-indexes-in-oracle-database (Accessed: March 15, 2023).