Category Archives: Writing

How Databases Work

In this post, we will explore how databases work. There are number of databases including SQL and NoSQL, but we will mostly be talking about relational databases.

Introduction

Every time, I have used databases for queries, I have wondered how the databases work internally. Coming from programming languages background, it is easy to understand on the surface.

A user writes a query with certain syntax, the code gets compiled into machine code with grammar and an interpreter executes the machine code. That’s a simple understanding.

Databases Internals

In short, databases have frontend of Interface, SQL Command Processor and Virtual Machine.

And there is a backend of B-Tree, Pager and OS Interface.

This particular architecture is specific to SQLite database, but most of the other SQL (relational) databases work in the similar ways.

Overview of Database

Let’s dive into the overview of the database internals. In previous section, I showed the architecture that contains frontend and backend components. Let’s look at those components and what they do

A user types SQL query using user interface. SQL query goes through three stages tokenizer, parser and code generator.

From the written SQL query, tokenizer creates identifiable tokens. These tokens are then parsed in attribute grammar for the language. Code generator takes the generated grammar to create virtual machine bytecode.

Virtual-machine then takes operations generated from bytecode and stores in a data structure B-Tree. Virtual Machine is a big switch statement.

B-Tree consists of many nodes and each node is a page. B-Tree retrieves a page from disk or saves the page to disk by issuing a command to Pager.

Pager does the majority of work of reading and writing in the database files. OS Interface is an OS dependent layer and helps Pager in reading and writing the data in files. Depending on the OS of server where the database is running, OS interface can function differently.

Understanding B-Tree

Database uses B-Tree data structure to represent table and index.

B-Tree is a data structure that allows efficient data storage and retrieval.

Search for a specific value is O(log n) for time complexity.

Insert OR Delete a value is also O(log n) for time complexity.

Space Complexity while using B-Tree is also O(n).

B-Tree is a self-balancing tree that keeps the data sorted. Having sorted data allows fast search and insertion or deletion operation.

The main difference between Binary Tree and B-Tree is that B-Tree can have more than 2 children.

B-Tree properties

  1. Every node has at most m children
  2. Every node except root and leaves has at least m/2 children
  3. Root node has at least 2 children unless it is a leaf node
  4. All leaves appear on the same level
  5. A non-leaf node with k children contains k-1 keys

Binary Search

  • Each node contains a sorted array of keys.
  • Binary search is used within each node to find key.
  • It reduces the number of comparisons needed within nodes.

The way search works in B-Tree is as follows:

  • Search starts at the root node.
  • Use binary search to find either the key if it exists in current node OR find the correct child node to traverse next
  • Repeat the process until key is found or leaf is reached.

Conclusion

In this post, we shared the internals of database and how database works. If  you want to read more about SQLite DB, you can visit the official documentation here.

Blind Alley

I am using my blog platform to announce the publication of my second book Blind Alley. It took me close to a year to write the book, edit it, work with an editor, submit it to publisher and then publish it. Slowly I am getting hang on the whole process. What I am not good at yet though, is marketing. And hopefully, I will focus on that in near future.

Blind Alley

But why Blind Alley?

I started to write some short stories, there was a common theme that came out of those short stories was about social and cultural issues. When I finished the first editing of the draft, I started to read Asimov’s short story named Blind Alley. Even though the context of his work and my work was completely different, the title made more sense. In our current times, we follow what society has made a kind of rule. We blindly follow. We don’t question any of the beliefs or existing set expectations. As a writer, as a creator, I had a hard time with this. I continued to wrestle with different ideas and expectations. But I am not someone who would follow something for the sake of it. All those questions culminated in the stories of this book. Blind Alley gives an idea about the beliefs we should be questioning. We shouldn’t be expecting the right answer, but I do not see, why we can’t question them.

Thank You

I just want to say thank you to all those who read my first book 500 Miles. Continuing on this literary journey, I want to be grateful to all those people who support me and encourage me to write more.

Where can you buy Blind Alley?

If you are in India, you can buy the book on the following links:

Amazon: Amazon
Flipkart: Flipkart
WFP Store: White Falcon Publication Store

If you are in the US or any other part of the world, you can buy the book on the following links

Amazon US
Amazon UK
Canada Amazon

If you are an ebook reader and want the book on Kindle, you can buy it here