The Evolution of Database Systems: Indexing, Transactions, and Concurrency

12.1 The Thirty-Year Cycle of Database Technology

12.1.1 One Standard, Then Many: The 1980s to 2005

Before touching any technical detail, this session asks a career-level question: why are we studying database systems at all, what is the progression of the database industry, and how can a student prepare for the changes that will arrive in the next three, five, or ten years? The honest framing is that anyone serious about a career in database systems needs to see the whole arc — not just the current tool. A student who knows only today's tool is exactly like a photographer who knows only film: they are unprepared the day the industry changes.

Over the last 30 years, from the 1980s until 2005, relational database systems enjoyed complete domination — a genuine hegemony. Before that, network databases and other designs were tried, but relational systems won. A hegemony (a situation where one approach dominates everything else so completely that alternatives are marginal) describes what relational databases held for three decades. The language SQL and the frameworks around it became so famous that it was effectively the de facto standard — the standard in practice, even if no committee officially declared it — and everyone worked in SQL. One, two, or three commercial software products provided clean, convenient access to relational data. Microsoft Access is deliberately left out of that list — it was never commercially significant, only useful for learning.

Then in 2005 something drastic happened: the mass adoption of cloud computing software and the mass use of big data applications. The pattern across the industry is regular — roughly every decade or fifteen years there is a complete overhaul of the technology. The rule of survival is simple: if you cling onto the new technology, you survive; if you do not, the industry leaves you behind.

12.1.2 The Wave Pattern: GUI, Internet, Big Data, Generative AI

The same wave has repeated four times, each time rewarding the companies that embraced it.

Companies that had been doing fine with earlier technologies were suddenly in a new world; any technology or industry that used computers with GUIs survived — or rather thrived — and the others were left away. In the 1990s every industry had to decide: do we embrace the internet, or do we keep doing what we are doing? The ones that used it to their advantage survived and thrived; the rest fell behind. From 2005 to the present the wave has been big data and smartphones.

12.1.3 Why the Cycle Matters to You

The relevance to a student is twofold. First, you need to be agile. If you work in the industry and keep watching how it moves, you can be better prepared and better equipped for each shift. Second, and deeper: every wave still builds on the same fundamentals. The internet helped SQL become very, very famous. When big data arrived, the limitation was how data can be kept, how it can be scaled, and how it can be used across machines. Each new generation of systems solved those problems differently, but the underlying ideas — storing data, retrieving it fast, keeping it correct under concurrency — stayed constant. The person who understands one era's technology at the ground level is the one who adopts the next era easily.

This is the point where the course's big arc starts: everything after this — indexing, transactions, and concurrency control — is the reusable core beneath the waves. As a career matter, a database engineer who understands how a B+ tree works and why transactions need isolation can walk into any new database product, from MongoDB to a blockchain store, and decode it quickly. That adaptability is the real return on studying this material.

12.2 The Big Data Era and the Rise of NoSQL

12.2.1 The Limits That Big Data Exposed

As big data applications arrived, relational systems hit three walls: how data can be kept, how data can be scaled, and how data can be used across many machines. A single database server has finite disk, finite memory, and a finite processor; when the data outgrows one machine, the questions "where does this byte live?", "how do I split the load?", and "how do I keep copies consistent?" stop being theoretical.

The solution providers and entrepreneurs responded with their own file systems. Facebook is one of the most famous later examples, and before Facebook, Google and Yahoo had already created their own file systems. Out of that came Hadoop as a very famous application: many commodity systems are pooled into a cluster, and the cluster provides a lot of computing power. Commodity systems — cheap, off-the-shelf hardware rather than specialized mainframes — make the economics work: one big machine is expensive, but a thousand ordinary machines are cheap. Managing a database across many commodity systems is a serious challenge, and the Hadoop file system handled it nicely; the Google file system did the same thing at a different front.

Even with distributed file systems in place, users still wanted something that could be used as easily as SQL. That gap produced MongoDB, one of the first big NoSQL answers. Seven or eight years ago even many people with over a decade of industry experience had not heard of MongoDB to any famous extent; in the last five years it has become the kind of thing that everyone and all the applications use.

It helps to state the trade-off explicitly. A relational database system provides reliability and a very stable system. The normalization work — minimum redundancy, maximum certainty in the data — is exactly what buys that stability. (Remember the earlier lectures: normalization removes redundant copies of facts so that a fact is stored once, which is what makes updates safe and the data trustworthy.) But the applications that appeared after 2005 and up to now wanted something different: more and more scalable, faster and faster to use. That demand produced the NoSQL database paradigm we are seeing. The concept of NoSQL existed way back, over two decades ago, but its use in the enterprise industry has really only taken off in the last five to seven years.

12.2.2 The New Players: MongoDB, Cassandra, Neo4j

The market has gone from one player before 2005 to several distinct players now, and each new database has its own advantage and overcomes a specific limitation of RDBMS-style databases.

MongoDB rules one type of database — the document-oriented type: data is kept as documents, each document being a self-contained bundle of fields, which maps naturally to the way application code already structures objects. In graph databases, Neo4j is a dominant player: it stores nodes and the edges between them as first-class citizens, so a query like "who are the friends of my friends" walks edges directly instead of joining tables. Cassandra is another player in this space. Note on classification: the professor places Cassandra among the document databases, while the standard classification treats Cassandra as a wide-column store (data in rows addressed by key, with columns grouped into column families) — the practical point stands either way: each player specializes in a different shape of data and a different access pattern. Each has its own distinct advantages, and each overcomes a specific limitation that RDBMS-type databases had.

The practical consequence: whenever a new project arrives at your organization, it is you who has to decide — and propose to your team — why the project should switch to a particular database, and what that switch saves in the long and short point of time. That decision power is the reason to understand this landscape: the engineer who can justify a database choice with reasons, not fashion, is the one whose proposals get approved.

12.2.3 Matching the Database to the Workload

The database you need depends on your end use case, and three contrasting workloads make the point.

The same logic applies to the famous names: how IRCTC handles its database is very different from how Instagram handles its database, and both are very different from how a traditional website like Amazon handles its database.

When you build a solution, you first decide what your priorities are — "I want maximum transactional efficiency per unit point of time" — and then you pick and choose from the available packages accordingly.

12.2.4 The Two Career Paths This Opens

There are two ways this knowledge turns into value.

That is the central message of this part of the course — rather than remaining a user of SQL and of the software providers, understand how the software actually works: how it analyzes the code you write, how it executes it, how it optimizes it, and how the low-level systems behave. Everything discussed after normalization — indexes, transactions, concurrency — exists to build that understanding. The course keeps coming back to one question about every topic: why are we discussing this, and how can we use it for our advantage?

When a student wonders whether any of this affects their employability or their dollar value, the answer is the paradigm argument in reverse: niche technologies multiply — for a particular industry, sector, customer type, programming language, or integration platform there will be new database software — and the person who understands the fundamentals of any one of them adapts to all of them.

12.2.5 Security Is a Broader Word Than It Looks

12.3 Blockchain: A Different Kind of Database

12.3.1 The Question That Started It

The student's question hides the assumption this section dismantles: that the database world splits into exactly two camps, RDBMS and NoSQL. In fact the space is wider — blockchain is a third family with a different job. The test to apply to any new storage technology is not "is it like SQL?" but "what does this use case need?" Blockchain answers the use case that says: the records must be impossible for any single party — even the owner — to quietly rewrite.

12.3.2 Trust in Code: The Blockchain Pitch

Blockchain's core offering is trust delivered by code instead of by people or institutions. In a traditional database the operator is trusted: the bank that keeps your ledger, the company that keeps your orders. Blockchain replaces that institutional trust with a structure where the record-keeping rules are enforced by the system itself. The concrete mechanisms:

The history is concrete: the first Bitcoin blockchain came into being in 2009, and Ethereum in 2016 (the two dates were run together in the discussion; the standard dates are Bitcoin's blockchain going live in 2009, and Ethereum launching in 2016). Since then there has been steady advancement in blockchain technology.

12.3.3 A Slow Database That Keeps Changing

Looked at as a database, blockchain is itself one — and an early one was considered a very slow database, block-level, without much more than that. The slowness is structural, not accidental: distributing every record to many parties and verifying every block by consensus costs far more than one machine reading its own disk. The paradigm is now changing with Solana, consensus-based chains, and other blockchains coming into the picture.

Even inside the blockchain industry the designs differ deeply:

• Solana handles its data with proof of history — a way of producing a verifiable order of events without full two-way communication at every step — so the way it creates trust and stores data is its own.
• The EVM-based systems, like Ethereum, are transaction-based systems: the Ethereum Virtual Machine executes transactions one by one under the rules of the chain, and how they handle data is completely different again.
• Newcomers in the space — spoken as "Apptoss", read as Aptos, a separate layer-1 blockchain — are different even within that specific industry.

For enterprise-level blockchain development there is an abundance of choice: what language to use, what software to use, and how the database aligns with a particular industry are all decisions you must make with awareness.

12.3.4 What This Means for the Future of Databases

The outlook the discussion paints: up to 2005 there was one thing; from 2005 to 2015 multiple things arrived; from 2015 to now there is an abundance of technologies at the cusp. The floodgates may open in the next three to five years, with very specific, very micro-specific database software arriving — including databases shaped around how particular blockchains handle data.

In the wider field, blockchain databases are where database research meets distributed-systems research: the ledger itself is a distributed log, and consensus protocols are the concurrency control of that world. The student who understands conventional transactions will meet the same anxieties — conflicting writers, ordering, durability — wearing different names on a blockchain.

12.4 Indexing: The Problem, the Mechanism, and the Payoff

12.4.1 Why the Course Spends Three Sessions on Indexing

On the surface, indexing looks like one line of SQL — create index on that particular attribute — and yet the course spends three class sessions on it. The types alone are many: hash-based indexing, indexing on B-trees and B+ trees, bitmap indexing, sparse index, dense index, clustering index, and more; and among those there is single-level and multi-level indexing, and much more besides. If all a user ever does is write create index, why study the field in such detail?

The answer is the same as before: once you know how these indexes work — once you know how the file system works — you can easily adapt to any particular technology. And if you are creating software rather than merely using it, you are far more likely to create optimized software for your own systems. Even while studying any tool, be aware of what assumptions and constraints you are relying on: today you run a one-tier architecture, tomorrow a client-server application on a network, later a completely new paradigm — the awareness is what survives the change.

12.4.2 The Physical Problem: Seek Time and Transfer Time

The problem indexing solves is physical. A file is stored on the hard disk in blocks — chunks of data — and the data sits in a place separate from where it is processed. To answer a query, the processor must find out which blocks in the file are relevant, move the disk head to that particular area — seeking to the right track and sector — and bring the blocks into main memory, where the actual processing can happen.

Two costs appear:

Generally, seek time is an order higher than the access time:

$$t_{\text{seek}}\gg t_{\text{access}}\text{(seek time is an order higher than access time)}$$

"An order higher" means roughly ten times larger: the mechanical positioning of the head (milliseconds) dwarfs the electronic transfer of the data once positioned (fractions of a millisecond). The reference treatment confirms this: the seek is called "the main culprit for the delay involved in transferring blocks between disk and memory," with average seeks of 4–10 ms versus transfer times of a fraction of a millisecond per block. So the goal of an index is to make seeking very, very fast. The index acts as a shortcut: instead of scanning everything, you look at the index and jump to the right blocks.

12.4.3 Worked Scenario: Finding Students Who Scored 10–11

This is the problem indexing came into existence to solve: the same data, same query, but the number of expensive seeks collapses from "every block" to "the few blocks that matter."

12.4.4 The Index Solution and Its Cost

Instead of finding all the data and bringing it into main memory, you create an index on one or two attributes. Based on that index, you look at the index and search the file system and the blocks much faster, going straight to what is relevant.

The trade is honest: it takes time to create an index, and it takes a huge amount of effort and resources to maintain that index. That extra cost is recovered by usage — if the index is used more and more, the chances are very high that very soon the effort has been paid back, and from that point onwards there is pure advantage.

What type of index to apply — B+ tree, bitmap, hash, sparse, dense, clustering — is a secondary front: once you understand the problem, you also need to know how to solve it.

The analogy can be stretched to any field where processing or decision making happens in a different place from the work itself — a supply chain is one such example — and you can extend the analogy with your own constraints and your own optimality focus. In a warehouse, the goods (data) sit far from the packing bench (processor), and a well-organized catalog of locations (the index) beats walking the aisles (the scan) every time the same items are picked repeatedly.

12.4.5 Beyond Relational: Indexing Everywhere

This universality is the deep reason the physical picture matters. The data being at a separate place from the processing, the blocks on disk, the seek and transfer costs — that problem is the same in every storage system, whatever its name. In the wider field, this is why search engines and document stores build inverted indexes, why graph databases index on node properties, and why even blockchains keep auxiliary lookup structures: every system, relational or not, faces the same physics.

12.5 Hashing: One Science, Many Applications

12.5.1 The Domain and the Buckets

Hashing as a concept is the same thing everywhere: a huge range exists in which data can appear, but the actual values in hand are few. Say the domain of data runs from one to ten thousand:

$$\mathcal{K}=\{1,2,\dots ,10,000\}$$

The actual values present are only 15. One value is 5, another is 500, another is 700, and the other 13 range somewhere in between.

When values are inserted and deleted sporadically, it is better to have a chunk of data or a cluster of data, rather than one exact spot per value. So we make clusters — buckets holding 1 to 100, 100 to 200, and so on:

$$B_1=\{1,\dots ,100\},B_2=\{101,\dots ,200\},\dots$$

and create a hash function that stores each data value into a particular bucket. When a bucket has a collision, we do something with those collisions.

12.5.2 Worked Example: 15 Values in a Domain of Ten Thousand

12.5.3 Collision Resolution: Chaining, Open Addressing, Multiple Hashing

Three collision-resolution techniques were covered in the data-structures material: open addressing, chaining, and multiple hashing (the name "multiple hashing" is kept as spoken; it is the rehashing-style family where a second hash or probe sequence is used).

In both chaining and multiple hashing, an overflow space is used: every data record gets an overflow pointer, and when a bucket overflows, the record follows the pointer chain to the next slot and sets the record there.

12.5.4 Hashing in Data Structures Versus Hashing in Databases

The first exchange is a clean statement of the course's core idea: the science transfers, the application differs. The second is an honest boundary — the in-course model of indexing is one thing, the ecosystem of external search and index tools is another, and understanding the former is the prerequisite for judging the latter.

In the wider field, hash-based indexing powers key-value stores and hash indexes in relational engines, while the same bucket-and-collision ideas reappear in distributed systems as consistent hashing — the mechanism that decides which machine in a cluster stores which key.

12.6 Transactions: The Problem of Concurrent Access

12.6.1 When Two People Touch the Same Data

The next big topic after indexing is transactions and concurrency. The problem: a database can be accessed by many people at one point of time. When one person wants to write to the database while somebody else is reading it at the same time, there can be discrepancies in the order in which somebody is accessing and somebody is writing. When that order matters — when it can really alter the output of the application — you need to be very careful.

Real-world: a railway reservation system, a hotel reservation system, a flight booking — whether a flight is booked or not, whether a booking is available or not, whether a seat is there or not, what the hotel rates are — all of it depends on how the database behaves under concurrent access. If thousands of people are accessing the database, each one should still feel like the only person using it.

12.6.2 The Book Price Example

12.6.3 Real Systems That Live and Die by Ordering

The same pattern scales to systems where money and availability are on the line. IRCTC's database, railway and hotel reservations, flight availability, seat availability, hotel pricing — all depend on the order in which thousands of concurrent accesses are applied. If the order breaks, a customer pays for a booking that another customer just took, or a seat is sold twice. In these systems the ordering problem is not academic; it is the product. The booking engine's entire reason to exist is to apply thousands of overlapping requests in an order that leaves every seat and stay accounted for exactly once.

12.6.4 The Illusion of Being Alone

The requirement is stated in one line: with thousands of people accessing the database, it should appear as if you are the only one accessing it. If you perform the same operation today and maybe tomorrow, you should still get the same output, provided nobody else is working at that point of time — which is never the reality, since other people are always working at the same time. So the user must get the feeling of sole access. The order in which accesses happen can impact the performance and also the quality of the response that another person receives — and that is the situation these mechanisms exist to handle.

12.6.5 Two Mechanisms: Locking and Timestamps

The naive answer to the problem is to freeze the database: while one person accesses it, others wait; once the person exits, the next one uses it. That is one way to start, and two concrete mechanisms implement the discipline:

These are the two mechanisms by which multiple people can access the database and still keep the user experience within a tolerable limit.

12.6.6 Student Questions and Answers

The student's paraphrase captures the failure exactly, and the professor's answer names the four properties the mechanisms must deliver — a preview of the next section: everyone works in isolation (isolation), all or nothing (atomicity), constraints respected (consistency), changes remain (durability). The rest of the course's transaction material is, in one sentence, how to make those four promises hold when thousands of accesses interleave.

12.7 ACID: The Four Properties

A transaction is a collection of operations that forms one logical unit of work — for a user it is "book this room"; inside the database it is dozens of reads and writes. The four ACID properties are the promises the database makes about every transaction. The acronym comes from the first letters: Atomicity, Consistency, Isolation, Durability. The lecture introduces them one at a time, and the order matters: isolation is the experience, atomicity is the failure rule, consistency is the state rule, durability is the persistence rule.

12.7.1 Isolation

The first property: even when multiple people access the database at the same time, everyone should feel that they are working in isolation — as if no one else exists in the system. The user's experience is that of a private database, even though thousands of operations are interleaving behind the scenes.

12.7.2 Atomicity

The second property: either everything works across, or nothing works across. The forbidden outcome is the split failure — "your money is debited, but the room is not reserved." A transaction must land as one indivisible unit: all of its effects happen, or none of them do.

12.7.3 Consistency

The third property: the system needs to be consistent. The constraints before and after need to be respected. If there are 10 seats, only 10 seats should be reserved — the database may never reach a state that violates its own rules, no matter how many transactions run at once. Consistency is the property that keeps the database meaningful between operations.

12.7.4 Durability

The fourth property: whatever happens after the person has accessed the database, the changes should remain on that database. A committed change survives — it is not lost when the access ends, when other users work, or when the system settles down. The output you were promised stays the output.

12.7.5 Why the Mechanisms Are Necessary

These four properties — atomicity, consistency, isolation, durability, the ACID properties — are the contract that concurrent execution is expected to ensure.

12.8 Assignment and Evaluation Guidance

12.8.1 The Evaluative Components

The evaluation for the course rests on four components: the mid-semester examination, quiz one, quiz two, and the projects. Mid-semester results (regular and makeup) are being processed; the notification channel has changed this time, which has delayed them, and once marks appear, feedback and justification will be available for discussion — evaluation is done with proper justification. The project description is posted on the Takshila portal as a notice and also in the team folder.

12.8.2 The Assignment: SQL Logic, Not an Application

The problem statement is real: it comes from business work done in 2021–22, shaped after 100 interviews and proper customer discovery — not something invented out of thin air — so treat the problem seriously. Whether assignment and project are separate entities is left to you, in your best judgment; any reasonable approach is acceptable.

12.8.3 Format: Handwritten, Typed, or Mixed

12.8.4 The Plagiarism and AI Policy

12.8.5 Student Questions and Answers

Exam Guidance Summary

• The course evaluation has four components: mid-semester, quiz one, quiz two, and the projects.
• The project assignment requires SQL logic only — no web application, no front-end stack (HTML, CSS, JavaScript, React, Redux). Write the SQL and include a snapshot of the SQL.
• An architectural design (ER) diagram is required for the assignment; any drawing tool, PowerPoint, Word, or pen and paper is acceptable.
• Submissions may be handwritten, typed, or mixed; there is no page-count heuristic. Depth of content matters more than verbosity, and presentation in tables is encouraged because it is easier to grade.
• The assignment problem statement comes from real 2021–22 business work shaped by 100 interviews and customer discovery — engage with it as a real problem.
• Plagiarism and AI-use checks apply; the checkers detect AI usage and cross-assignment matching. Work must be done honestly and individually; the policy is judgment-based around the reported percentage, not automatic punishment.
• Mid-semester marks (regular and makeup) are pending due to a change of the notification channel; feedback and justification will be available once the marks are published.

Key Industry Applications

• Real-world: relational hegemony until 2005 — SQL and its frameworks as the de facto standard for three decades; Microsoft Access noted as learning-only, not commercial.
• Real-world: the four technology waves — GUI operating systems (1980s), the internet (1990s), big data and smartphones (2005 onwards), generative AI (now); Kodak as the cautionary example of a former hegemony wiped out by the next wave.
• Real-world: Google and Yahoo built their own file systems; Hadoop pooled commodity systems into clusters; the Hadoop file system and Google file system managed data across them.
• Real-world: MongoDB went from unheard-of seven or eight years ago to being used by all the applications in the last five years; Cassandra and Neo4j lead other database niches.
• Real-world: workload-driven database choice — IRCTC, Instagram, and Amazon represent three different access patterns; the 200-users-a-day, one-million-search-users, and gigabytes-per-minute workloads each demand different systems.
• Real-world: blockchain as a database — Bitcoin (2009) and Ethereum (2016), DAOs, trust-in-code, tamper-evident trails; Solana with proof of history, EVM-based systems, and newcomers such as Aptos; IPFS as block-level storage.
• Real-world: indexing everywhere — relational, NoSQL (MongoDB, Cassandra), graph, and even blockchain databases all answer the same "how do we access data faster" question; third-party tools such as Sphinx exist outside the database engine itself.
• Real-world: transactional correctness in IRCTC railway reservations, hotel and flight booking systems, and Amazon-style price updates under concurrent users.