—

Database Design and Applications

Indexing for Fast Retrieval: Primary Indexes, B-Trees, and B+ Trees

Published: 2026-08-06

Level: postgraduate

Audience: Postgraduate students of database design and applications

13.1 Weak Entities, Relational Conversion, and Functional Dependencies

13.1.1 The Question: Can Weak Entities Be Normalized?

Hook. You built an ER diagram, hit a weak entity, and wondered: this thing has no key of its own — so how on earth do I normalize it to 3NF or 4NF? The answer turns out to be: you normalize the relational schema, not the ER diagram — and the conversion from ER to relations happens first.

The session opened with a doubt that had surfaced while students were solving their assignments. When an ER diagram contains weak entities, is there any way to normalize them to third or fourth normal form? The worry was specific: a weak entity has no key of its own, and even when a key that points to the owner entity type is present, that key repeats inside the weak entity. So how does the usual normalization machinery apply?

Q: When we are doing our assignments we came across one scenario — when we have some weak entities, do we have any ways and means to actually normalize them to third or fourth normal form, because we will not have a key over there? And even if we have a key which is pointing to the owner entity type, the key may be repeating in the weak entity. Is there a way to really go for a normalization for those kinds of designs?

A: Two clarifications are needed here. Once we are having an ER diagram, when there is a weak entity in that diagram it needs to be converted to a relational schema in such a way that the owner entity's primary key and the weak entity's distinguishing key are both taken to form the key, including all other attributes. Once we have converted the ER diagram to a relational schema, the ER discussion is over at that point of time; from that point onwards the discussion of normalization starts. Normalization operates on the relational schema, not on the ER diagram.

The answer separates the problem into two distinct discussions that must not be mixed.

Discussion 1 — conversion. A weak entity in an ER diagram must be converted into a relational schema. The owner entity's primary key and the weak entity's distinguishing key (its partial key) are both taken, and all other attributes are included.
Discussion 2 — normalization. Once that conversion is done, the ER-diagram discussion is over. From that point onwards, the normalization discussion starts, and normalization operates on the relational schema that the conversion produced.

In other words: conversion first, normalization second, and each has its own rules. A weak entity never "enters" normalization directly; what gets normalized is the relation that the conversion step produced — and that relation does have a key, formed from the owner's primary key plus the weak entity's partial key.

Assumption: the conversion rules above assume the standard mapping for weak entity types: total participation of the weak entity in the identifying relationship, and the owner contributing its primary key. If a weak entity has multiple owners (for example, a DEPENDENT identified by the combination of EMPLOYEE and a plan), then the primary keys of all owners join the partial key to form the relation's key. The idea is unchanged: the weak entity's own attributes never form a key by themselves.

13.1.2 Converting a Weak Entity into a Relation

The conversion works like this. Consider a weak entity $W$ with attributes $a$ , $b$ , and $c$ , where $c$ is the distinguishing attribute — the partial key that helps tell weak-entity instances apart within one owner. There is an owner entity $O$ with a primary key and, possibly, other keys.

The owner side is straightforward: the owner entity becomes a relation $O$ that has its own primary key plus its other attributes. Nobody struggles with that part. For the cardinality that connects them, assume total participation of the weak entity and one-sided participation on the owner side.

The weak entity becomes a relation $W$ that contains:

the primary key of the owner entity $O$ , which is added as an attribute of $W$ ,
the distinguishing attribute $c$ ,
the remaining attributes $a$ and $b$ .

The composite of the owner's primary key and the distinguishing attribute together identify every record of the weak entity. This is why weak entities need their owner: by themselves, their attributes cannot tell their own instances apart.

Formalize. If the owner's primary key is written $K_{O}$ and the weak entity's distinguishing attribute is $c$ , then the key of the converted relation $W$ is the composite

$K_{W} = (K_{O}, c)$

with every other attribute of $W$ — here $a$ and $b$ — carried along as non-key attributes. Each symbol: $K_{O}$ (the primary key of the owner entity type, e.g., the employee ID), $c$ (the distinguishing attribute, also called the partial key — the attribute that separates instances within one owner), and $(K_{O}, c)$ (the composite key, whose two components together must appear nowhere else in the file). Notice what is not in the key: the weak entity's own plain attributes $a$ and $b$ . If the weak entity has several owners, $K_{W}$ grows to the union of all owner primary keys plus $c$ .

Worked example — the two Nehas. Suppose $W$ is a dependent, $O$ is an employee, and the attributes are name, date of birth, and gender.

Step 1 — owner relation. The employee becomes relation EMPLOYEE with its primary key, say emp_id.
Step 2 — weak relation. DEPENDENT gets the attributes: emp_id (owner's primary key, added as a foreign key), name, dob, gender.
Step 3 — key. The distinguishing attribute among name, dob, gender — say name — is the partial key. So the key of DEPENDENT is (emp_id, name).
Step 4 — the test. In one organization, employee A and employee B could each have a child named Neha, born on the same date, with the same gender. The three attributes — name, date of birth, gender — cannot distinguish the two children from each other across the whole set of records.

emp_id	name	dob	gender
A	Neha	2015-04-12	F
A	Rohan	2018-09-03	M
B	Neha	2015-04-12	F

Rows 1 and 3 are identical on (name, dob, gender) — but never identical on (emp_id, name). The two Nehas are no longer confused because each row carries the employee ID of the parent who owns that dependent. The composite key (emp_id, name) distinguishes every record uniquely.

Sense-check: if the same employee A had two children named Neha, even (emp_id, name) would collide — then a different distinguishing attribute (say, dob) would have to be picked for the partial key, which is exactly why the distinguishing attribute is chosen so that within one owner the values never repeat.

Pitfall — normalizing the ER diagram instead of the relation. A weak entity has no key of its own, so any attempt to "check 2NF" on the ER diagram itself is meaningless. The check only becomes meaningful after the conversion produces a relation with the composite key $(K_{O}, c)$ . Students who skip the conversion step end up confused about "where the key is."

Pitfall — thinking the repeating owner key is a problem. The owner's primary key deliberately repeats in every dependent row belonging to that owner. That repetition is not redundancy to be removed; it is the mechanism that ties each dependent to its owner and forms half of the composite key.

13.1.3 Defining Functional Dependencies First

When the discussion moves to second, third, and fourth normal form, all of them are decided by functional dependencies — and functional dependencies are something the designer must specify for themselves. There is no automated way to conjure them from an ER diagram. The instructor's phrasing was direct: when we try to reach second, third, or fourth normal form, we ourselves need to write these functional dependencies; without them, we cannot take any decision on second normal form, third normal form, fourth normal form, or BCNF, whatever it may be.

Formalize. A functional dependency (FD), written

$α \to β$

means: whenever two records agree on the attribute(s) in $α$ (the left-hand side), they must also agree on the attribute(s) in $β$ (the right-hand side). In plain terms, $α$ determines $β$ . Every symbol: $α$ and $β$ are sets of attributes (they may hold one attribute or several), and the arrow $\to$ reads "functionally determines."

Three terms appear in every normal-form rule and are worth fixing now:

Candidate key: a minimal set of attributes that uniquely identifies a record — remove any attribute and it no longer does.
Prime attribute: an attribute that is part of at least one candidate key.
Super key: any set of attributes that contains a candidate key (it may have extra attributes).

This connects to a deeper point about database design: a good design needs proper semantics. Naming attributes $a$ , $b$ , $c$ is a poor design; the names should carry meaning — write them out as name, date of birth, gender, and so on. Semantic naming is exactly what lets a designer notice functional dependencies in the first place. In the dependent example, whenever the name repeats, at least the gender repeats too — that observation itself is a functional dependency: name determines gender. Once such dependencies are written down, the normal-form checks become mechanical.

Intuition + analogy. Think of functional dependencies as the rules of the world the designer writes on a contract before the database is built. Normalization is a machine that takes two inputs — the relation and the FD list — and answers "which normal form is this relation in?" If the FD list is empty, the machine has no rules to check and answers nothing. That is why the professor's answer was "Definitely yes — first we define the functional dependencies, and then the discussion of normal forms goes on."

13.1.4 The Second and Third Normal Form Rules

The normal-form violations were restated in the instructor's own words, and they are worth holding onto as a decision procedure.

Second normal form violation: a full functional dependency $α \to β$ where $α$ is not a complete candidate key — that is, $α$ is only part of a candidate key — and $β$ is not a prime attribute. If both conditions hold, the relation violates second normal form.
Third normal form violation: a transitive dependency $α \to β$ where, given the relation is already in second normal form, $α$ is not a super key and $β$ is not a prime attribute. If both hold, the relation is not in third normal form.
BCNF: the left-hand side $α$ needs to be a complete super key.

The instructor's phrasing of 2NF: "alpha is not a complete candidate key and beta is not a prime attribute". The phrasing of 3NF: "alpha is not a super key and beta is not a prime attribute" — with the 2NF check already satisfied before this one applies. BCNF is stricter still: $α$ must be a complete super key, with no exceptions.

Formalize — the three checks as a decision ladder. To decide the normal form of a relation $R$ with a known FD set $F$ :

2NF check. For every FD $α \to β$ in $F$ : if $α$ is a proper subset of some candidate key (a partial dependency), and $β$ is a non-prime attribute, then $R$ is not in 2NF.
3NF check (only if 2NF passed). For every FD $α \to β$ in $F$ : if $α$ is not a super key, and $β$ is a non-prime attribute, then $R$ is not in 3NF. This is the transitive dependency case: the dependency chains through an attribute that is neither a key nor prime.
BCNF check (only if 3NF passed). For every FD $α \to β$ in $F$ : if $α$ is not a super key, then $R$ is not in BCNF. Notice: BCNF does not care whether $β$ is prime. A transitive dependency whose right-hand side happens to be a prime attribute still violates BCNF — this is exactly where 3NF and BCNF diverge.

Check	Condition for violation	Left-hand side condition	Right-hand side condition
2NF	partial dependency	$α$ part of a candidate key, not the whole	$β$ non-prime
3NF	transitive dependency	$α$ not a super key	$β$ non-prime
BCNF	any bad FD	$α$ not a super key	— (any $β$ )

Worked example — applying the ladder. Take a small relation for course enrollments, ENROLL(student_id, course_id, instructor, instructor_office), with candidate key (student_id, course_id) and FDs:

FD1: (student_id, course_id) → instructor (the pair determines the instructor)
FD2: instructor → instructor_office (one instructor has one office)

Check 2NF: is any FD's left-hand side a proper part of the candidate key? FD1's left side is the whole key — fine. FD2's left side, instructor, is not part of the candidate key at all — so it is not a partial dependency; 2NF holds.

Check 3NF: FD2 has $α =$ instructor, which is not a super key, and $β =$ instructor_office, which is not prime (instructor_office is in no candidate key). Both conditions hold — the relation violates 3NF by a transitive dependency: student_id, course_id → instructor → instructor_office.

Fix: split into ENROLL(student_id, course_id, instructor) and INSTRUCTOR(instructor, instructor_office). Every left-hand side (the candidate key, and instructor in the second relation) is now a super key — the result is in BCNF.

Sense-check: the office no longer repeats with every enrollment, so updating an office changes exactly one record — the classic reward of normalization.

Pitfall — checking 3NF before 2NF. The 3NF rule in the professor's phrasing explicitly assumes the relation already satisfies 2NF. Running the 3NF test on a relation that fails 2NF gives garbage — the transitive-dependency definition presupposes no partial dependencies remain.

Pitfall — memorizing BCNF as "3NF plus prime β." Many students remember "BCNF = 3NF and no transitive dependency where β is prime." Simpler and safer: in BCNF, every FD must have a super key on the left, with no exceptions and no conditions on $β$ .

Q: So we need to define the functional dependencies first, and only then can we say whether the relation is in second, third, or other normal forms?

A: Definitely yes. First we define the functional dependencies, and then the discussion of normal forms goes on. Without the dependencies written down, none of the normal-form decisions can be made.

Recap. Weak entities are converted to relations first (owner key + partial key form the composite key); normalization then runs on that relation, driven entirely by functional dependencies the designer writes down. The decision ladder: 2NF bans partial dependencies, 3NF bans transitive dependencies onto non-prime attributes, BCNF bans every dependency whose left side is not a super key. Bridge: the next question — can a designer add arbitrary attributes to change all of this? — leads straight into the bigger picture of what a database is for.

13.1.5 Arbitrary Keys and Surrogate Identifiers

Q: What if we introduce an arbitrary key — for example, a relationship ID that is just a sequential number created only to uniquely identify a record? Will that have an impact on the normalization of the system?

A: Yes, that is correct. You can always introduce different attributes. You understand this yourself now — you are coming to a very important point. Within a project, you are free to introduce any variable that is not against the conditions and that meets the functionality of the application. It can be any relation ID and so forth.

The deeper principle: a database designer is allowed — and often encouraged — to add attributes such as sequential relation IDs to make the schema behave well. These surrogate identifiers change the functional-dependency picture, and so change what normal form the schema ends up in. The freedom is bounded only by the application's constraints. This question also set up the rest of the session, because the instructor used it to zoom out and show the whole application in which a database lives.

Formalize. A surrogate identifier (surrogate key) is a synthetic attribute — typically an auto-incrementing integer — added purely to identify records, carrying no real-world meaning. Because a surrogate key alone is a candidate key of size one, it changes the functional-dependency picture immediately: any FD whose left side is a proper part of the old composite key now becomes a partial dependency on the new key (or disappears entirely, if the dependency is absorbed). Either way, the normal form of the schema can change — that is why the answer is "yes, it has an impact."

Pitfall — surrogates are not a licence to ignore semantics. A surrogate key does not erase the real-world FDs (instructor → instructor_office still holds). It can mask a normalization problem, not remove it. And the rule from the answer still binds: the extra attribute must not violate the application's conditions — every constraint of the application stays in force.

Scope — where this freedom ends. The designer may add attributes freely within a project, as long as they meet the application's functionality and violate no constraint. Outside that contract — for example, inventing keys that break referential integrity or lose audit information — the freedom does not apply.

Recap. Surrogate identifiers are legitimate designer tools: they give every record a one-attribute key, reshape the functional-dependency picture, and can move a schema into a better normal form — bounded only by the application's constraints. The healthcare-records project that follows shows exactly why a designer's freedom matters: the database has to satisfy a real application's purposes.

13.2 The Application Big Picture: Where the Database Lives

13.2.1 Client, Application, and Database

Hook. A database is never alone: it is one component inside a much larger application, and the designer's job only makes sense once you can see the whole system it serves.

To see why a designer is free to add attributes, it helps to see the entire system that the database serves. An application is hosted at some server that has its own IP address. The server can live inside an organization, it can be a third-party server the organization hosts on, it can be a cloud application with its own address, or it can run on a blockchain — wherever the application is deployed, it has an address. A client system — a mobile phone, a desktop, anything else — requests the application, and the application is fetched across.

When the application is loaded, one of its components is the database. Many other components surround it: face authentication, access to third-party services such as GPS, microservices the team created or consumes, and an API that provides a nice interface for using the system. When a user requests something, the application runs code. If the user asks for something, the application fetches from the database and sends the response back. The application's code always interacts with the database to get responses. The database itself can sit on a central server's secondary storage devices — HDD or SSD — and so on.

Intuition + analogy. Think of a restaurant. The client is the diner, the application is the kitchen plus the waiters, and the database is the cold storage room in the back. The diner never walks into the cold room; the waiter takes the order, the kitchen fetches ingredients from the storage room as needed, and the plate comes back out. In the same way, user requests go to the application code, which fetches from the database whenever data is needed — the client never talks to the database directly. Where the analogy breaks: the kitchen (application) can also cook without storage (serve cached or computed answers), and the storage room (database) can serve several kitchens (multiple services) at once.

The request path, named. The full chain in one line: client request → application code (running at the server's IP address) → database lookup on secondary storage → response returned through the application and back across the internet. The database sits on the secondary storage — HDD or SSD — of the central server, which is precisely why "how fast can the database answer" will dominate the rest of this lecture.

13.2.2 The Healthcare Records Scenario

The bigger picture is this. A client comes to the team — the database designer and administrator — and says: "I am creating an application where I want to store the healthcare records of patients, with some anonymity, and so on. Now create the complete application."

The designer's checklist, whether or not a front end is in scope:

The database must interact with the application and retrieve responses in the minimum possible time.
It must allow as much concurrency as possible.
It must always give the correct answer.
All constraints of the application must be respected.
Relations must be created so that common attributes exist between relations for easy retrieval.
There must be no spurious tuples — no tuples that join together by accident.
Nothing may violate the rules and regulations of the application.

For this project, the work is only the database part. A front end that enters values, searches values, and displays values could have been requested too, but even without it the goal is the same: the database meets its purposes and respects every constraint. The front end and back end are separate; the application itself would be written in Java, Python, or any other language, continuously receiving client requests, processing them, and — when required — fetching data from the database and replying.

Worked example — the anonymized healthcare database. The client asks for patient healthcare records with anonymity. Translate each requirement into a concrete design decision:

Minimum response time → indexes on the attributes that frequent queries filter on (the subject of the rest of this lecture).
Maximum concurrency → design the schema and access patterns so many users can read and write without blocking each other (the later transaction-management topic).
Correct answers always → constraints that the DBMS enforces: primary keys, foreign keys, NOT NULL, CHECK.
Respect constraints → e.g., a patient's records must never outlive the patient row; deletions cascade correctly.
Common attributes between relations → every relation that must join easily shares a key, e.g., patient_id appears in PATIENT, VISIT, and PRESCRIPTION.
No spurious tuples → attributes are placed in relations by functional dependencies and normalization (Section 13.1), so a natural join never produces accidental combinations.
Anonymity → personal identifiers are kept separate or masked so analytics queries do not expose names — the "user names hidden" note from the campaign discussion in 13.3.

The result is one coherent contract: every design choice — schema, keys, indexes — exists to satisfy one or more of these seven requirements. The designer's freedom from Section 13.1 (adding a relation ID) is exactly this contract in action: the attribute is allowed because it helps meet the application's purposes without violating a constraint.

Sense-check: each checklist item maps to a concrete, testable property of the schema; if a requirement has no artifact in the design, the design is incomplete.

Pitfall — building only the front end. The front end (enter values, search values, display values) is separate from the back end; the database work is its own deliverable. A common mistake is to treat the UI as the project and defer the schema — but the seven requirements above are all database-side, and they are the contract the designer is actually paid to meet.

Pitfall — forgetting "no spurious tuples." Two relations with no common attributes can still be joined syntactically; the result is every possible pair — meaningless rows that "join together by accident." Guarding against this is a schema-quality requirement, not an afterthought.

This is also why arbitrary relation IDs are legitimate: the designer's contract is to meet the application's purposes and constraints, and any extra attribute that helps do that without violating a constraint is fair game.

13.2.3 Security: Injection and Cross-Site Scripting

Q: Is there any topic on security — forming SQL queries, or cross-site scripting attacks, which are very common and prominent?

A: We are not teaching how to reduce vulnerabilities or stop injection attacks in this course. But the basic idea is that we need to ensure there are no possibilities that, within an SQL query, something is introduced — some person passes some data which then gets executed in the system. We need to take care of it at our level, even though the detailed topic is not part of this course.

Formalize. SQL injection is an attack where user-supplied input is concatenated into a SQL statement and executed as part of it — the input stops being data and becomes code. Cross-site scripting (XSS) is the web equivalent: user-supplied content is rendered by other users' browsers as executable script instead of as plain text. Both share one root cause: the system fails to separate data from instructions. In the professor's phrasing, the essential rule is that nothing a person passes in should ever get executed inside the system.

The instructor added a real-world note: a software product for detecting cross-site scripting vulnerabilities was built a couple of years ago — a patent was filed around it — and used in a project for the Data Science Council of India, checking websites across multiple companies, from different banking organizations to various others. The takeaway for this course is narrower: user-supplied data must never become executable SQL, and the designer should keep that principle in mind even though the full defense is a separate subject.

Pitfall — concatenating user input into queries. Even in this course's scope, the designer's own schema and application code must avoid building SQL strings by pasting in user text. The professional defense — parameterized queries, prepared statements, output encoding, input validation — is a separate specialty, but the designer's responsibility to flag the boundary is not.

Recap + bridge. A database lives inside an application: client requests flow through application code to the database on secondary storage, and the designer's contract is a seven-point checklist of speed, concurrency, correctness, constraints, joinability, no spurious tuples, and no rule violations. Bridge: that checklist demands fast retrieval from secondary storage — which is slow by default. The next section sets up exactly how slow, and why an index is the answer.

13.3 The Retrieval Problem: Why Search Is Slow Without an Index

13.3.1 The Scale of Real Workloads

Hook. A hundred thousand records sound large — but a real application's data grows every day, and the queries against it must answer in milliseconds. Where does the slowness actually come from?

The transition into indexing started from a concrete workload. Suppose a database holds data for 10,000 users, and every user's data is stored at least 5, 10, 15, 20, or 35 times a day. Multiply that across users and days, and the record count grows continuously. Now consider what applications do with that volume:

Launch a campaign — properly anonymized, with user names hidden — that targets a particular demography or sentiment: how much people's health is improving, how much exercise they do, how much sleep they have, whether a particular type of disease is emerging. A smart-watch seller wants to target the emotional side of that data.
A hospital wants to query a lot of records at once.

Either way, a request arrives at the application and has to fetch records very fast — joins, selections, projections, and much more. With hundreds of thousands of records, finding anything is itself a tedious task. The raw search over 100,000 records is slow before any optimization is applied.

Worked example — how the file grows. Take the lower end: 10,000 users, each adding 5 records a day.

Day 1: $10, 000 \times 5 = 50, 000$ records.
After 20 days: $50, 000 \times 20 = 1, 000, 000$ records — a million records within three weeks.
At the upper bound (35 per user per day): day 1 alone already gives $350, 000$ records.

The 100,000-record figure from the lecture is only a small snapshot of a live system. Every subsequent cost figure (block counts, search steps) multiplies with this growth, which is why the "retrieval must be fast" requirement of Section 13.2 is not optional.

Sense-check: with linear growth the file crosses six digits within days — confirming that "search everything" cannot survive at this scale.

13.3.2 Blocks, Seek Time, and Locality of Reference

Why is raw search so slow? In the architecture at hand there is a processor that works very nicely with main memory, and the data lives on secondary storage — a hard disk, HDD or SSD form. To process a record, the system must go to the secondary storage, locate where the data is stored, go to that particular block, fetch the entire block into main memory, let the processor process it, and then return the response through the application and out across the internet.

Formalize. Data is transferred between disk and memory in fixed-size blocks (also called pages). If a block holds $b$ records, then a file of $r$ records occupies

$⌈ \frac{r}{b} ⌉$

blocks, where $⌈ \cdot ⌉$ is the ceiling function (round up — a partially filled last block still costs a full block access). The blocking factor $b$ is $⌊ block size / record size ⌋$ . Two costs dominate every access: the seek time (moving the read/write head to the right track) and the read/write time (transferring the block's bytes); on a spinning disk the rotational delay (waiting for the disk to rotate the right sector under the head) joins them. The key property: a block access is not proportional to the number of records fetched — it costs the same whether the block holds one wanted record or forty.

This builds on the earlier discussion of disks: the disk and spindle rotate to keep the head on the right track and sector, and retrieval happens block by block. One block on the disk holds the data, and a block of the same size is allocated in main memory. Data is not fetched record by record. This block-sized transfer exists because of locality of reference: once one record is fetched, other nearby records are likely to be needed too, so the whole block is kept.

Intuition + analogy. Locality of reference is why you take the whole drawer from the filing cabinet, not one sheet. If someone asks for a customer's order, the other orders of the same customer (or the same day) are usually wanted next — so the system hauls the drawer (block) into memory and keeps it. The analogy breaks when queries truly touch scattered single records: then whole-drawer transfers waste bandwidth, which is exactly what indexing (and later, hashing) is designed to avoid.

Two costs matter enormously: the seek time (moving the head to the right track) and the read/write time (transferring the data), and both must be minimized. There is one more ordering problem: the system must first find where the record is. Unless it knows which block the data resides in, it has to examine everything. One previous session solved part of this with hashing, which stores records appropriately for fast lookup. In this session the tool is indexing.

13.3.3 The Index as the Answer

Instead of searching all the hundred thousand records, the database can create an index out of them. The whole discussion that follows — what index to create, how indexes make retrieval faster, how the index itself is accessed, and what problems different indexes have — is the subject of this and the following sessions on indexing and fast record retrieval. The instructor flagged that this is roughly the second, third, or possibly fourth session on this topic.

Recap + bridge. Real workloads grow into the hundreds of thousands of records within days; records are moved in blocks because of locality of reference; and every block access costs seek plus transfer time. The only way to keep retrieval fast is to stop examining everything — which is precisely what an index does. Bridge: the simplest such structure is the primary index, built on a sorted file.

Pitfall — assuming RAM-like access. A common beginner mental model is "the data is in memory, so searching is cheap." On secondary storage, a single block access costs thousands of times more than a memory access, and the cost does not scale with the record count per block. All the counting that follows (13 accesses vs 4) is about disk block accesses — the right unit to optimize.

13.4 The Primary Index

13.4.1 Ordering Field and Key

Hook. If the data file is already sorted on an attribute, a tiny side-table of "first key per block" can cut a search from thirteen disk accesses to four. That side-table is the primary index.

The primary index is the simplest index to visualize, and it depends on two properties of the data file. Take a student record with attributes such as ID, name, email ID, phone number, and address. If the records are physically stored in sorted order on one particular attribute, that attribute is the ordering field. In the example, the physical storage keeps all records sorted by ID — the file starts with ID 1, then 2, then 5, then 9, and so on.

If the ordering field is also a key — every value in the field is unique — then an index created on it is called a primary index. Sorted order plus uniqueness makes the designer's task easy, and it is exactly this combination that the rest of the mechanics relies on.

Formalize. Given a data file $F$ with fields ID, name, email, phone, address:

Ordering field: the field on which the records of $F$ are physically stored in sorted order. At most one such field can exist per file — the physical records have exactly one order.
Ordering key: an ordering field that is also a key (all values distinct). A file can have at most one primary index or one clustering index, but not both, because both require the same physical ordering.

The primary index definition in one sentence: an index created on an attribute that is stored in sorted order within the secondary storage and is also a key attribute.

Real-world note: this is the same distinction that shows up in everyday SQL usage. CREATE INDEX on an attribute creates an index; whether that index is a B-tree, B+ tree, hash index, or bitmap index is decided by the database software. The user-level command hides the mechanism.

13.4.2 The Anatomy of an Index Entry

The data file is stored in blocks. Suppose each block holds 10 entries; the last entry of one block has ID 101, and the next block starts at 109, and another block starts at 510, and so on. An index is built by picking up the first value of each block — 1, 109, 510 — and creating an index entry for it.

Each index entry stores two things:

the key value — the ordering attribute value of the first record in the block,
the pointer — the address of the block that contains the record with that key value.

The index so has one key value and one pointer per data block. Even though each data record has many attributes, the index is created on only one attribute, so the index is much smaller than the data. A small index is cheap to keep in memory and cheap to search.

Formalize — the entry form. Every index entry is a pair

$⟨ K (i), P (i)⟩$

where $K (i)$ is the key value of the anchor record — the first record — of block $i$ , and $P (i)$ is the disk-block address of block $i$ . The first record of each block is called the block anchor. Number of entries = number of data blocks (sparse by design — see 13.5). The first three entries for the student file: $⟨ 1, block 0 ⟩$ , $⟨ 109, block 1 ⟩$ , $⟨ 510, block 2 ⟩$ .

Why the index is small, twice over: there is one entry per block, not per record; and each entry carries only two fields (key + address) against a record's five fields.

Worked example — size comparison. Data file: 100,000 student records, 10 per block → 10,000 blocks. Primary index: one entry per block → 10,000 entries. If a data record is 100 bytes and an index entry is 11 bytes, the data file occupies 10,000 × 4,096 bytes ≈ 41 MB of blocks, while the index occupies roughly 10,000 × 11 ≈ 110 KB of blocks — under 0.3% of the data size. A structure this small can sit in main memory, and searching it costs almost nothing.

Sense-check: one index entry per block, 11 bytes each — the arithmetic is 10,000 entries × 11 bytes; the index is two orders of magnitude smaller than the data.

Pitfall — thinking the index stores the data. The index holds only the anchor key value and the block address; the actual records live in the data file. Deleting a record does not delete anything from the index — the block address stays valid — though the anchor can change (see the deletion discussion below).

Pitfall — assuming one entry per record. A primary index deliberately stores one entry per block. An index with one entry per record is a different creature — the dense index (13.5).

13.4.3 Student Questions: SQL Indexes, Pointers, and Index Tables

Q: Is this similar to the indexes we create in an SQL database?

A: Very good question. In SQL we have very little provision to say what type of index is created. The statement create index on that particular attribute just creates an index on that attribute; that is all it does. What type of index it is — whether it is stored as a B-tree, B+ tree, hash index, or bitmap index — is a deeper discussion about how the index is stored and accessed. The database software takes care of what the index looks like. Our discussion goes one level deeper, because you might one day work in an organization that builds such software. Given the move towards specialization, we need to be aware of how indexes are created and how they are used.

SQL gives one command — CREATE INDEX — with almost no say over the mechanism. The storage engine decides the index type (B+ tree by default in commercial engines; hash, bitmap, and others available). This course studies the layer the SQL command hides: what the index physically looks like and how it is accessed, because that is what engine-builders and performance specialists must know.

Q: Will the pointer point to a number of records, or to some other data structure which is itself an index?

A: Correct — that is another type of index that we create, and that is also possible. When an index is not stored in sorted order, we create another data structure to store it. That discussion comes later. It is quite likely: when things are created on a particular index that is not stored in sorted order, we have to do something like that.

Q: Data and index storage are two different things. Record creation may happen at a different time than index creation — you may decide to create the index later while the data is not in sorted order. But typically most index types, like B-tree, keep the index values sorted. Am I right?

A: Absolutely. Maybe not hash, but otherwise absolutely.

Q: If we create an index later, once the database is live, the DBMS will create an index table — what the key is and what the address is — created dynamically. Also, when we delete a record, it is deleted from the original physical disk itself; the block becomes completely free, and the index is adjusted appropriately.

A: Both things are correct. We might create an index later; the index is created in a dynamic manner — depending on what type of key we use, sorted or not sorted, the DBMS decides what to do. And whenever we delete something, we need to ensure the index is also updated or edited, so that things are updated completely.

Q&A — pointers and maintenance, consolidated. The pointer in an index entry is a block address; when an index is built over unsorted data, the pointer may instead lead through another data structure (a level of indirection) — the professor confirmed that possibility explicitly. Two further confirmations: (1) the DBMS creates the index table dynamically, on demand, and the structure chosen depends on whether the key is sorted; (2) every delete must be mirrored in the index — the block becomes free and the index entry for that block's anchor is updated or removed, so the index and data never drift apart.

13.4.4 Indexes and Joins

Q: Indexing is done to reach records faster. But will indexing actually work in case of a join, or will the join query take its own time?

A: This is a very good question — it fills in something not yet mentioned: indexes are created for faster retrieval, faster storage, and faster access; it is all for efficiency. In joins, although full query processing and optimization is not part of this course, this is what happens: all SQL queries are converted into relational algebra, the relational algebra query is converted into a tree, and that tree decides how the data is accessed. When an index exists, the seek time and normal access times become relatively very fast. Without an index, finding the values that meet a predicate takes longer; with an index it becomes very fast. The same holds for sorting the entire database on an attribute — with a key it becomes really fast.

For joins specifically: when joining two relations, one is the inner relation and one is the outer relation. The inner relation is kept in the processor or in main memory as much as possible, and every block of the outer relation is brought in one block at a time. If an index exists on the inner or outer relation, the system fetches only the matching entries instead of bringing everything in and then checking for matches. When the join is on the indexed attribute — the common attribute of a natural join — the speedup is especially large. The same applies to intersection or conjunction (AND) operations on the indexed attribute: there is no need to retrieve everything and intersect the values; the index can be examined directly, and with a dense index even portions of it.

Formalize — the query pipeline. SQL text → relational algebra → operator tree → execution. The tree is the plan: it fixes the order in which files are scanned, sorted, and joined. An index changes what the tree can do at the file access level: an equality predicate on an indexed attribute becomes "probe the index, fetch the matching block(s)" instead of "scan the whole file." In a nested-loop join, the inner relation is held in memory as much as possible and each outer block is fetched once; an index on the inner relation's join attribute turns each outer tuple's lookup from a full inner scan into a handful of block accesses.

Pitfall — expecting an index to fix every query. An index helps predicates and joins on its own attribute. A join on an unindexed attribute still degrades to scanning; a predicate on another attribute ignores the index entirely. And the index itself must be maintained — the effort side of the effort-reward trade (13.4.5).

13.4.5 Effort and Reward

Q: Indexes are for faster retrieval and access and reducing the search times, but indexes have another purpose too: ensuring integrity constraints. For example, the primary key is also a type of index, and unique keys and foreign key indexes are indexes too. They improve access performance, but you also need them to enforce integrity constraints. Is that right?

A: The instructor chose not to comment at that moment, saying the point may be discussed further if it comes up again.

The general principle that was endorsed: everything in this area trades effort against reward. Creating an index and maintaining it — updating it on inserts, deletes, and updates, as the deletion discussion just showed — is effort. That effort is appropriately rewarded only if retrieval becomes much, much faster than the time and energy spent creating and maintaining the index. This mirrors the normalization discussion: normalization takes effort and the reward is minimal redundancy and good data; indexes take effort and the reward is fast access.

Recap. A primary index = one $⟨ K (i), P (i)⟩$ pair per data block over a sorted key field — anchor key value plus block address. It is tiny, searchable, and maintained dynamically by the DBMS; it speeds predicates, joins, and sorts on its attribute; and it costs maintenance effort that must be repaid by retrieval speed — exactly the normalization trade.

Exam note (integrity, deferred). The student's observation that indexes double as integrity-enforcement structures (unique/primary key indexes exist partly to reject duplicates) is accurate in commercial engines, but the instructor explicitly deferred it — expect the course treatment of indexes to be about speed, with the integrity role either unexamined or phrased as "not commented on in the session."

13.5 Sparse, Dense, and Clustering Indexes

13.5.1 The Three Flavors

Hook. "Dense" and "sparse" sound like they describe repeated versus unrepeated values — the professor's poll-style correction says no. The real distinction is far simpler: are index entries created for all values, or only for some?

The primary index created one entry per block, which is a sparse index: not every record gets an index entry. But other flavors exist, and the choice depends on the attribute being indexed.

Dense index: an index entry is created for every value of the indexed field — one entry per record. This is what happens when indexing a field on which all distinct values get their own entry.
Sparse index: index entries exist only for some values — for example, the first value of each block. A sparse index requires the underlying attribute to be in sorted order; otherwise the missing entries cannot be located and the pointers make no sense.
Clustering index: the indexed field is a non-key field — its values repeat. If the records are sorted on that field and one index entry is created per distinct value, all records sharing a value form a cluster behind a single entry.

The hostel example made clustering concrete. Suppose the address attribute stores just the hostel name. Many students are in Ram Bhawan, many in Meera Bhawan, many in others — the same value repeats across many records. If these entries are in sorted order, the index does not store an entry for every student; it creates one entry per distinct hostel name, and that single entry points to the block where the records for that hostel begin.

One clarification the instructor made matters: a dense index is dense because it covers all entries (every value), and a sparse index is sparse because it skips some entries — for example, no entry is created for the finance one and no entry for the physics one. The "repeating values" property is not what makes an index sparse; sparseness is about skipped entries.

Formalize — the taxonomy on two axes. An index flavor is decided by two independent questions: coverage (entry per value vs entry per block/distinct value) and field type (key with unique values vs non-key with repeats). The three single-level ordered indexes:

Index	Field	Number of first-level entries	Dense or sparse
Primary	ordering key	one per data block (block anchors)	sparse
Clustering	ordering non-key	one per distinct value	sparse
Secondary (key)	non-ordering key	one per record	dense
Secondary (non-key)	non-ordering non-key	one per record or per distinct value	dense or sparse

Worked example — hostel clustering. A student file ordered by address, where address holds only hostel names: Ram Bhawan, Meera Bhawan, and so on. The distinct values, in sorted order:

Index entry	Block pointer
Meera Bhawan	block holding the first Meera Bhawan student
Ram Bhawan	block holding the first Ram Bhawan student

Twenty students in Ram Bhawan spread across three blocks produce exactly one entry. A query "all students in Ram Bhawan" goes to the index, follows the single pointer to the cluster's start, and reads the consecutive blocks that contain the cluster.

Sense-check: the number of entries equals the number of distinct hostels, not the number of students — that is what "one entry per distinct value" means.

Q: Then a dense index is one where the values are repeating, and a sparse one is where they are not repeating?

A: Not exactly — a dense index is one where I am creating an index for all the values, all the entries; a sparse index is one where I am not creating entries for all of the attributes, so some entries are skipped. That is the distinguishing factor. Repetition of values is what makes the index a clustering index instead, not what makes it dense or sparse.

The correction is worth fixing permanently: dense = an entry for every value; sparse = some entries skipped. Repetition of values is the defining property of a clustering index, an entirely different axis. The two axes (coverage, field type) are independent, and mixing them up loses marks.

Pitfall — calling the primary index dense. The primary index has one entry per block, not per record — it skips the vast majority of records, so it is sparse (nondense). Dense indexes appear only when every record gets an entry.

Pitfall — assuming a sparse index works on unsorted data. Sparse requires the field to be in sorted order: the whole point is to search between anchors. On unsorted data, skipped entries mean unfindable records — pointers make no sense (the professor's exact phrasing).

13.5.2 The Combinations

The flavors combine with the ordering and key properties of the field to give a small taxonomy:

Index on a key that is stored in sorted order in the secondary storage — the primary index.
Index on a key that is not stored in sorted order — possible, but the index must be built differently. The email-ID example: emails are sorted by first letter — all entries with a, then b, and so on — yet the pointers may fly all over, matching records that live in unsorted data blocks. The index values themselves are sorted, but the data blocks are not.
Index on a non-key field stored in sorted order — the clustering index, with one entry per repeated value.
Index on a non-key field not in sorted order — also possible.

The instructor's summary of the mental model: the index has values in sorted order, each value with a pointer — that is all an index is. Different attributes give different flavors: key or non-key, sorted or unsorted, dense or sparse.

The instructor also noted that in an open-book setting, students need not memorize the names sparse and dense. What matters is visualization: an index is created on different attributes, and depending on those attributes, the index takes different forms.

Pitfall — thinking an index is only for sorted data files. The professor's taxonomy shows otherwise: a key that is not stored in sorted order (case 2) still gets an index — the index values are sorted and hold pointers that "fly all over" the unsorted data blocks. What changes is the search procedure, not the possibility.

13.5.3 Where the Index Lives

Q: Where is the index stored?

A: The index is generally stored in the physical or secondary storage as well. Take a database with 100,000 records and maybe 10,000 blocks: all of these are in secondary storage, and the index is also stored in secondary storage. We might require pulling the entire index into main memory to access it.

The index is itself a file on secondary storage, not in RAM. Because it is far smaller than the data (one entry per block, two fields each), it is cheap to pull entirely into main memory for searches — which is exactly why the small size of a primary index is a design win.

13.5.4 Student Questions and a Deferred Promise

Q: In a sparse index, do the data records reorganize?

A: Let us see what a sparse index is. In a sparse index we are not storing entries for all values. The entries that we do store must be in sorted order; otherwise we would not have a correct idea of which entries we are missing. So when you look at a sparse index, the attribute on which the index is created is at least in sorted order. Otherwise some entries would be missed and the pointer would make no sense.

Q: For a sparse index, will performance still be effective when the search key is not present in the index — and what happens when we insert a record?

A: (Deferred.) That is a very powerful question. The instructor deliberately chose not to answer it immediately: "I will answer you how the indexes are created and stored and the problems with that." The answer comes right after the worked examples, in the discussion of multi-level indexes and the pain of insertion and deletion — that is, in the motivation for B-trees.

The deferral is worth tracking as a thread through the rest of the lecture: inserting a record into a sorted sparse-indexed file means creating index entries at every level of a multi-level index (13.7.1), and the work only grows with more levels — which is the exact pain the B-tree was built to remove (13.8).

Recap + bridge. Three flavors: dense (entry per value), sparse (entries skipped, needs sorted data), clustering (entry per distinct value of a non-key). The real axes are coverage and field type — repetition defines clustering, not sparseness. Bridge: now that the index concept is fixed, the lecture turns to real numbers — how many block accesses each flavor saves, in the textbook's worked examples.

13.6 Worked Examples: What an Index Costs and Saves

13.6.1 The Setup: Ordered File, 300,000 Records

Hook. Thirteen disk accesses to find one record — with a four-thousandth-of-a-megabyte side table, the same search costs four. The three textbook examples in this section turn "indexes are good" into exact numbers, and the professor walked through all three live, urging students to follow along at pages 605, 606, and 609.

The textbook chapter on indexes — Chapter 17, starting at page 602 — contains three worked examples, and the instructor walked them through one by one, urging students to follow along in their own copies at pages 605, 606, and 609.

The setup for Example 1: suppose we have an ordered file where the number of records is 300,000, the block size is 4,096 bytes (data always moves in blocks of this fixed size), and the size of every record is 100 bytes.

13.6.2 Example 1: Binary Search Without an Index

Given 300,000 records, 100 bytes each, and a 4,096-byte block size, the first question is how many records fit in one block. The professor's verbal description: "4096 bytes it can store in every block and given that every record is 100 bytes I can store at max 40 records, 4096 divided by 40 and take a ceiling or take a floor for it."

Step 1 — records per block. 4096 bytes per block ÷ 100 bytes per record. Since a record must never be split across blocks (the unspanned assumption), take the floor:

$records per block = ⌊ \frac{4096}{100} ⌋ = ⌊ 40.96 ⌋ = 40$

Step 2 — total blocks. 300,000 records at 40 records per block:

$blocks = \frac{300 , 000}{40} = 7, 500$

Step 3 — binary search cost. The file is sorted by the search attribute (say the record with attribute value 76,543 is being located), and no index exists. Binary search halves the remaining block range at every step, so the worst case is

$block accesses = ⌈ lo g_{2} (7, 500)⌉ = ⌈ 12.87 ⌉ = 13$

because $2^{12} = 4096 < 7500 \leq 8192 = 2^{13}$ . Baseline: 13 block accesses with no index at all.

Sense-check: each access halves the search space — 7,500 → 3,750 → 1,875 → 937 → 468 → 234 → 117 → 58 → 29 → 14 → 7 → 3 → 1: twelve halvings plus the final read of the one remaining block is 13 accesses. The count checks out.

13.6.3 Example 2: With a Primary Index

Example 2 repeats the same retrieval with an index created. The index entry — the key value plus the pointer — is assumed to total 11 bytes. The professor's verbal description: "the size of this particular entry and the pointer is assuming to be having total 11 bytes... I can in a particular block where in the block can have 4096 bytes and the entire one particular entry in the index contains 11 bytes so it would take 372 index entries per block."

Step 1 — index entries per block.

$index entries per block = ⌊ \frac{4096}{11} ⌋ = ⌊ 372.36 ⌋ = 372$

Step 2 — index blocks. The index contains 1,000 entries, as spoken in the session. Each block holds 372 entries, so the index needs

$index blocks = ⌈ \frac{1 , 000}{372} ⌉ = ⌈ 2.69 ⌉ = 3$

Step 3 — total block accesses. Search the three index blocks by binary search (three blocks → 2 accesses halving, roughly $⌈ lo g_{2} 3 ⌉ = 2$ , but the professor's counting takes the index search as reading the index blocks, then one more for the data block):

$block accesses with index = 3 + 1 = 4$

The contrast is the whole point: 13 block accesses without an index versus 4 with one — the professor's framing: "that's the power of storing that index."

Sense-check: the index is about 0.3% of the data's size (1,000 × 11 bytes vs 300,000 × 100 bytes), yet it cuts the search from 13 accesses to 4 — a 3.25× speedup on access count alone, before counting that each index block search is faster to transfer than a data block.

Notation and reading note (spoken vs strict arithmetic). The index of a primary index holds one entry per data block — so the strict reading of 7,500 data blocks would give 7,500 index entries, and

$⌈ \frac{7 , 500}{372} ⌉ = 21 index blocks (hence 22 accesses)$

The lecture's spoken count — 1,000 index entries, 3 index blocks, 4 accesses — is the version the professor used and the version to expect on the exam; the strict one-entry-per-block reading above is the standard-form relationship from the reference treatment, shown here for completeness. When solving an exam numerical, use the numbers as given in the question.

The general formulas, collected. These four patterns recur in every numerical of this type:

$records per block = ⌊ \frac{block size}{record size} ⌋$

$data blocks = ⌈ \frac{records}{records per block} ⌉$

$binary search (no index) = ⌈ lo g_{2} (data blocks)⌉$

$index blocks = ⌈ \frac{index entries}{index entries per block} ⌉, accesses with index = index blocks searched + 1$

13.6.4 Example 3: The Multi-Level Index

The third example pushes the same idea one level up. Once the index itself grows large — say the index spans 300 blocks — even searching the index takes many block accesses (with 300 blocks, binary search costs $⌈ lo g_{2} (300)⌉ = 9$ accesses). The solution is to create an index on the index: since index entries are themselves sorted, a secondary index can be created on top of the first index, and that makes the process even faster.

Step 1 — the problem. The first-level index spans 300 blocks. Binary search over 300 blocks:

$⌈ lo g_{2} (300)⌉ = ⌈ 8.23 ⌉ = 9 accesses, plus 1 for the data block = 10$

Step 2 — the fix. Treat the first-level index as a sorted file and build a second-level index on it, with one entry per first-level block (block anchors again). If the second level fits in one block, searching it costs 1 access; then 1 access retrieves the first-level block; then 1 access retrieves the data block:

$1 + 1 + 1 = 3 accesses vs 10 without the second level$

Step 3 — when to stop. Add levels until some level fits in a single block — that block is the top index level, and each added level divides the search space by the blocking factor (the fan-out) instead of by 2. With a fan-out of 372 (from Example 2), a multi-level index needs about $⌈ lo g_{372} r_{1} ⌉$ levels for $r_{1}$ first-level entries.

Sense-check: 1,000 first-level entries at 372 per block → 3 first-level blocks → 1 second-level block: two levels suffice, exactly matching Example 2's 3+1 accesses.

This multi-level indexing only makes sense when the index spans enough blocks that searching it is expensive — when it takes 12 or 13 block accesses. If the index fits in a single block, there is nothing to gain. The professor's summary: "if the index does not store in a single block, that becomes expensive, so I create an index out of it first of all, then I create a secondary index on that index order; that's how things go across."

Pitfall — adding levels to a one-block index. A second level on an index that already fits in one block adds accesses without saving anything. Multi-level pays only when the base index spans many blocks — the professor's threshold: when searching it takes 12 or 13 accesses.

13.6.5 Reading the Textbook's Index

The instructor showed a study skill worth copying: the textbook itself has an index at the back. Searching for "primary index" there lists pages 602, 603, 605, and 606. Instead of flipping through every page of the book, you can go to the index, find where a topic is covered, and read exactly those pages. This is exactly the kind of fast lookup an index provides — the database equivalent of the index in a book. Students were told they can also snapshot Examples 2 and 3 for reference.

Q&A — the book index is a database index. The physical index at the back of a textbook stores <term, page-list> pairs and answers "which pages mention this term?" in one lookup instead of a page-by-page scan — the same idea as $⟨ K (i), P (i)⟩$ . It is also a genuine open-book exam skill: locate the topic in the index, jump to the pages, read.

13.6.6 Exam Notes: Numericals in an Open-Book Exam

Q: From the exam perspective, how will the questions be? Like Example 1 and Example 2 that you shared — will those page numbers be the only ones, or will you ask more numerical questions?

A: In the comprehensive exam you will find similar types of questions. This is an open-book examination, and in an open-book exam anyone can look things up — now you know how to read an index, go to that page, keep flipping, and write anything and everything you find. It is very hard to distinguish who has actually read and gone to the second level, third level, fourth level. Numerical questions are easier to distinguish: they tell how much you have practiced, and those who have practiced will get them. So expect more and more such numericals in the comprehensive examination. Conceptual things are also important, but numericals are the ones to expect more of.

Exam note: expect numerical problems modeled on these three examples — records per block, number of blocks, index entries per block, block accesses with and without an index — plus conceptual questions alongside. In an open-book exam, numericals are the discriminator: they reward practice. Know the four formulas of 13.6.3 cold, and practice on varied numbers.

13.7 Single-Level and Multi-Level Indexes: The Limits

13.7.1 The Insertion and Deletion Pain

Hook. The primary index made reading fast — but every insert and delete now has to touch multiple levels of bookkeeping. Static multi-level indexes buy speed at the price of painful updates; the B-tree exists to fix exactly this.

With a single-level or multi-level index built, consider what happens on insert. Adding a new entry means creating an index value at the bottom level, then another at the next level up, and so on through a two-level or three-level structure — several insertion operations for one new record. Deleting a record means deleting or updating entries at every level too. The professor's phrasing: "if the entry is added here I need to create an index value here and an index value here should be pushed all the way; if it is a two-level or three-level index, every entry needs to be created... and if I am deleting something, I have to delete not only here but update everything here as well, so it becomes a tedious task."

So even after the optimization of indexing, adding and deleting records is not an optimal operation in a multi-level index structure.

Formalize — the update cost. In a $t$ -level static index, one data-file insert may change the anchor of a block; that change cascades: the first-level entry must be rewritten, which may change that level's anchors, which propagates to the second level, and so on up to the top. In the worst case an insert or delete touches one entry at every level — $t$ index updates per data update — and if a level overflows, records must be shifted and the level's anchors rewritten entirely. The static structure has no slack: overflow has nowhere to go except an overflow area.

13.7.2 When Multi-Level Indexes Work Well

This structure is best for a database that is more or less stable — where there is little turbulence, few insertions and deletions. For such databases, single-level and multi-level indexes are good. But in general it is not guaranteed that data will be that calm, so an alternative is needed — and the alternative is the tree-based index.

Scope — the calm-data assumption. Static multi-level indexes (and their classic instance, ISAM, 13.7.5) assume a workload with few updates. If inserts and deletes arrive constantly, the overflow area grows, searches degrade from fixed index levels into longer and longer chain walks, and the file needs periodic reorganization. Any workload with continuous change needs the dynamic alternative.

13.7.3 Trees: The Next Step

Trees are familiar from other courses — data structures and similar — with AVL trees and red-black trees among the options. A tree has nodes, each node has children, and the children can have children of their own. One of the most striking properties is that trees do not contain cycles: a child node never links back to its parent. That is not acceptable in trees — not in AVL trees, not in red-black trees. Searching works by depth: start at the top, and as the search goes deeper through the levels, it becomes finer and finer, until the value is found.

A multi-level index can itself be seen as a form of tree: one multi-level index refers to next-level indexes, which are its children, and they have further children, until an entry or key points to the actual database blocks. But what this session actually studies is the B-tree, which has specific provisions of its own.

Intuition + analogy. A tree is a hierarchy like a family tree: every person has parents and children, and no one is their own ancestor — that is the no-cycles rule. Search descends the hierarchy and at every level the set of candidates shrinks, so depth equals precision: at the root the answer could be anywhere; four levels down, only a handful of candidates remain.

13.7.4 What Does the "B" Stand For?

The instructor ran a poll: what do you think B stands for? Students typed guesses freely — balloon, bat, binary, and anything else that came to mind. The point of the poll was participation, not correctness: typing something keeps you attentive, keeps you engaged, reduces distraction, and — when the right answer arrives — helps it stay with you longer. The answer: B means balanced tree.

There are various balanced trees. In an AVL tree, the height of any child subtree can differ from the others by plus or minus one — if the height of a node's subtree is 5, a child's height may be 4, 5, or 6. If one branch reaches depth 4 while a sibling branch has height 2, that is not a balanced tree. Balance means: for any particular child node, the heights are the same. The AVL tolerance of a height difference of one is acceptable there, but in a B-tree it is not — all leaves sit at the same level.

Formalize — two notions of balance. AVL balance: for every node, the heights of its two child subtrees differ by at most one — a local tolerance of $\pm 1$ . B-tree balance: all leaves sit at exactly the same level — a global equality, no tolerance. This single rule guarantees that every search from root to leaf costs the same number of block accesses, which is exactly what makes B-tree lookup time predictable.

13.7.5 ISAM: The Indexed Sequential Access Method

Before the tree indexes, the classic answer to the multi-level-index maintenance problem was ISAM — the indexed sequential access method, the static index structure used by IBM systems and early database engines. Its name says exactly what it does: data records are kept in sequential (sorted) order on the key, and a multi-level index lets the system jump to the right area instead of scanning. The earlier session's real-world note ("the index-sequential file — an ordered sequential file with a primary index — is the classic construction behind many textbook and legacy database storage designs") is ISAM.

The organization is a fixed, static hierarchy over the disk geometry. The data file is sorted by key and stored sequentially across the disk. Each cylinder holds an index of the tracks within it (a track index), the set of cylinder indexes is indexed by a cylinder index, and above that sits a master index — so a lookup descends the fixed index levels and then performs a short sequential scan within the final track: hence "indexed sequential." The structure is decided once at file creation, and its levels never move.

Formalize — the ISAM hierarchy. Lookup in ISAM: master index → cylinder index → track index → sequential scan of one track. The three levels mirror the disk's physical geometry (tracks inside cylinders on a disk pack), so each descent step reads exactly one index block and the levels are fixed at file creation. Compare with the general multi-level index of 13.6.4, which is the same idea abstracted away from the disk geometry.

This is exactly the static multi-level index whose insertion and deletion pain the session has just described — and ISAM is its perfect illustration. A new record that belongs in the middle of a full track cannot push the file around (the tracks are fixed), so it goes into a separate overflow area, chained to its proper position. Each insertion lengthens an overflow chain and each deletion leaves holes; as the file ages, lookups degrade from a fixed number of index levels to longer and longer chain traversals, until the file must be reorganized — re-sorted and rebuilt — to recover performance. ISAM is therefore ideal for a file that is created once, loaded, and then only read and rarely updated — the dictionary, the stable lookup table — and progressively worse for a file with constant insertions and deletions.

Pitfall — forgetting the overflow chains. ISAM's fixed tracks cannot grow, so inserts overflow into chained areas. Over time the chains lengthen and search cost grows — the "calm data" assumption of 13.7.2 made concrete. The remedy (reorganization) is expensive and must be scheduled, which is why ISAM suits static files.

Pitfall — writing the exam answer too thin. The syllabus asks for ISAM as a multilevel static index organization; the complete exam story is: static levels, sorted data, overflow area, reorganization — plus the contrast with the dynamic B-tree (splits and merges keep every level balanced all the time, no overflow area needed).

The historical lesson is the bridge to the next sections: the B-tree was designed to keep the same indexed-sequential idea — sorted keys, fast lookup by descent — while making insertion and deletion cheap by restructuring on the fly instead of relegating growth to an overflow area. Where ISAM is static (fixed levels, overflow chains, periodic reorganization), the B-tree is dynamic (splits and merges keep every level balanced all the time).

Recap + bridge. Multi-level indexes answer fast but update slowly: every insert or delete touches entries at every level, so they suit calm, stable files — ISAM is the classic static instance, with its overflow chains and periodic reorganization. The fix is a tree that restructures itself on every update: the balanced B-tree, whose leaves all sit at the same level. Bridge: the next section builds a B-tree by hand, one insert at a time.

13.8 B-Trees: Balanced Tree Indexes

13.8.1 The Structure of a B-Tree Node

Hook. A B-tree is a multi-level index that repairs itself: when a node fills up, it splits; when a node empties, it merges. One parameter $p$ controls everything — and the whole construction reduces to "never let a node hold fewer than half its capacity, and never more than $p - 1$ keys."

Like any index, a B-tree entry contains a key value and a pointer to the actual physical storage block where the record lives. The node structure is: a block pointer, then a key with its record pointer, then another block pointer, then another key with its record pointer, and so on, ending with a final block pointer. The block pointers reference other nodes — other blocks that contain further key-and-pointer entries.

The parameter $p$ controls the size of every node:

Maximum number of block pointers in a node: $p$ .
Maximum number of keys in a node: $p - 1$ . For $p = 4$ , that is 3 keys.
Minimum number of keys in every node: $⌈ p /2 ⌉ - 1$ . For $p = 4$ , that is $⌈ 4/2 ⌉ - 1 = 2 - 1 = 1$ key.

The professor's verbal description: "when I say p is equal to four that's the maximum number of pointers I can have... if the block pointers are at four, the maximum number of keys I can have in a block is p minus one, equal to three... the minimum number of keys that every block needs to have is p by two, whose ceiling I take, minus one."

Formalize — the node anatomy. An internal B-tree node is an alternating sequence

$⟨ P_{1}, ⟨ K_{1}, P r_{1} ⟩, P_{2}, ⟨ K_{2}, P r_{2} ⟩, \dots, ⟨ K_{q - 1}, P r_{q - 1} ⟩, P_{q} ⟩$

where each $P_{i}$ is a tree pointer (to another node), each $K_{i}$ is a search key, each $P r_{i}$ is a data pointer (to the record — or the block — holding that key), and $q \leq p$ . The rules:

Keys sorted within the node: $K_{1} < K_{2} < \dots < K_{q - 1}$ .
Subtree ranges: every key in the subtree pointed to by $P_{i}$ lies strictly between $K_{i - 1}$ and $K_{i}$ .
Capacity: at most $p$ tree pointers (hence at most $p - 1$ keys, hence at most $p - 1$ data pointers).
Fill: every node except the root and the deepest-level nodes holds at least $⌈ p /2 ⌉$ tree pointers — that is at least $⌈ p /2 ⌉ - 1$ keys.
Balance: the deepest-level nodes all sit at the same level, and they are structurally identical to internal nodes except that their tree pointers are NULL.

For $p = 4$ : max 4 pointers, max 3 keys, min 1 key per non-root node. The node is a block; each B-tree node is one disk block, so "how many nodes do I visit" is "how many block accesses."

Pitfall — confusing data pointers with tree pointers. $P r_{i}$ (data pointer) points to the record whose key is $K_{i}$ — it does not lead deeper into the tree. $P_{i}$ (tree pointer) points to another node. Every key in the tree carries a data pointer: "wherever the data is, it has a record pointer" — the property that the B+ tree (13.9) abolishes above the bottom level.

Pitfall — forgetting the root exception. The root may hold fewer than the minimum keys (a fresh tree starts as a single root node holding one key). The minimum-fill rule binds every other node.

13.8.2 Worked Example: Building a B-Tree for 1 to 10

The construction inserts the values 1 through 10 one at a time, with $p = 4$ .

Insert 1, 2, 3. The first block accepts 1, 2, and 3 — three keys, each with its record pointer. Three is the maximum, so the block is now full.

Insert 4. The block cannot hold four keys, so it overflows. The remedy is to take a median and promote it. The median can be 2 or 3 — either choice is correct, but the choice of ordering — left ordering versus right ordering — must be written down and followed consistently throughout the entire construction. The professor's left ordering rule: "when I am using left ordering, I would use this value to create a higher level." With left ordering, the median of 1, 2, 3, 4 is 2, which rises to a new root. The root block now contains 2 with its pointer. The pointer to the left of 2 leads to a block with all keys less than 2 — the single key 1. The pointer to the right of 2 leads to a block with all keys greater than 2 — the keys 3 and 4.

Insert 5. The right block becomes 3, 4, 5 — three keys, which fits.

Insert 6. The right block would become 3, 4, 5, 6 — overflow. Taking the median of 3, 4, 5, 6 with left ordering gives 4, which rises. The root now holds 2 and 4. Its left pointer leads to the block with 1; its middle pointer leads to the block with 3; its right pointer leads to the block with 5, 6.

Insert 7. The right block becomes 5, 6, 7 — three keys, which fits.

Insert 8. The right block would become 5, 6, 7, 8 — overflow. The median of 5, 6, 7, 8 with left ordering is 6, which rises. The root now holds 2, 4, 6 — three keys, the maximum. The blocks hold 1; 3; 5; and 7, 8.

Insert 9. The right block becomes 7, 8, 9 — three keys, which fits.

Insert 10. The right block would become 7, 8, 9, 10 — overflow. The median of 7, 8, 9, 10 with left ordering is 8, which rises. But the root already holds 2, 4, 6, and adding 8 would make 2, 4, 6, 8 — four keys, which violates the maximum of $p - 1 = 3$ . The root itself overflows, so the root splits: the median of 2, 4, 6, 8 with left ordering is 4, which rises to a brand-new root. This is the only time the tree gains a level.

13.8.3 The Final B-Tree and Its Properties

The complete B-tree for the values 1 through 10 with $p = 4$ looks like this:

                4
           /         \
         2             6, 8
       /   \         /   |    \
      1     3       5    7    9, 10

Every key shown carries its own record pointer, even though the drawing omits them. Every internal node has block pointers: the root 4 points to the blocks (2) and (6, 8); the block (2) points to the data blocks for 1 and 3; the block (6, 8) points to the data blocks for 5, 7, and 9, 10.

Property check. Every internal node holds between $⌈ 4/2 ⌉ - 1 = 1$ and $4 - 1 = 3$ keys — the node 6, 8 holds 2, the leaves hold 1 or 2, nothing is empty and nothing overflows. Every leaf sits at the same depth (two levels below the root) — the tree is balanced. Subtree ranges hold: everything under the left pointer of 2 is less than 2; under its right pointer, greater than 2; under the left pointer of 6, 8 lies 5 (less than 6); under the middle, 7 (between 6 and 8); under the right, 9, 10 (greater than 8).

Sense-check: searching for 7 descends 4 → 6, 8 → 7: three block accesses. Any key in the tree costs the same three accesses — balance made uniform. The static multi-level index of 13.7 needed an overflow area; here the split at insert 10 restructured on the fly, keeping the tree legal without any overflow chains.

13.8.4 Left Ordering versus Right Ordering

The consistency rule deserves emphasis. When the median splits a full node, the designer may choose the left median or the right median — "either it can be two or it can be three" in the first split — but the same ordering must be used at every split in the tree. Mixing left ordering in one split and right ordering in another produces a garbled, inconsistent tree. In the session, a drawing-tool glitch ("I have not selected the pen option") interrupted the construction once, and the instructor redrew the tree; students were asked to note the intermediate states and to flag any mistake in the sequence 1 through 10.

Pitfall — mixing orderings mid-tree. With keys 1, 2, 3, 4 either 2 or 3 is a valid median — but if one split promotes the left median and a later split promotes the right median, the tree can violate its own ordering or leave a node under-filled, and exam answers that mix orderings lose consistency marks. Declare "left ordering throughout" (or "right ordering throughout") before the first split and keep it.

Pitfall — misplacing the median at a root split. When the root itself overflows (insert 10), the same rule applies: median of 2, 4, 6, 8 is 4 under left ordering — the new root is a single key with two children, and the tree gains exactly one level. A common error is to keep both halves unbalanced (2, 4 | 6, 8), which would leave the root with two keys and children at different depths.

Recap + bridge. A B-tree node is $⟨ P_{1}, ⟨ K_{1}, P r_{1} ⟩, \dots, P_{q} ⟩$ : max $p$ pointers, max $p - 1$ keys, min $⌈ p /2 ⌉ - 1$ keys, all leaves at one level. Inserts overflow up the tree; the median rises; the root splits and the tree grows one level — exactly once in the 1-to-10 run. Bridge: the B+ tree keeps this machinery but moves every data pointer down to the leaves, buying larger fan-out and range queries.

13.9 B+ Trees: Data Only at the Leaves

13.9.1 The Difference Between B-Tree and B+ Tree

Hook. The B-tree's only real flaw is that data pointers sit in internal nodes too, wasting slot space and blocking cheap range queries. Move every data pointer down to the leaves, link the leaves together, and both problems vanish — that single move is the B+ tree.

The B+ tree is the variant that commercial databases actually use, and the difference from the B-tree is a single architectural rule: in a B+ tree, the data — and the record pointers to the data — reside only at the leaf nodes. Nothing above the leaves holds data. Root nodes and intermediate nodes contain only keys and block pointers; the block pointers do not repeat data. The keys at non-leaf levels exist purely to guide the search down to the right leaf.

Two consequences follow.

First, every key that appears in an internal node also appears in a leaf, because the actual data lives only at the leaves. In the B-tree, the professor's phrasing: "wherever the data is there, it has a record pointer, but in a B+ tree, whenever I have data, it only has record pointers only at the leaf node. So only in the leaf nodes the actual data is residing and the record pointer to that; all the root nodes and intermediary children will only contain the pointer and no data."

Second, each leaf node carries a pointer to the next leaf node — the leaf chain. This chain is what makes range queries fast.

Formalize — the two node types. Internal node (routing only):

$⟨ P_{1}, K_{1}, P_{2}, K_{2}, \dots, K_{q - 1}, P_{q} ⟩$

Each $P_{i}$ is a tree pointer; the $K_{i}$ are routing keys with no data pointers. Leaf node:

$⟨⟨ K_{1}, P r_{1} ⟩, ⟨ K_{2}, P r_{2} ⟩, \dots, ⟨ K_{q - 1}, P r_{q - 1} ⟩, P_{next} ⟩$

Each $P r_{i}$ is a data pointer to the record with key $K_{i}$ , and $P_{next}$ points to the next leaf — the leaf chain. Capacity rules match the B-tree ( $p$ pointers, $p - 1$ keys, $⌈ p /2 ⌉ - 1$ minimum keys), but they apply to the leaves for data and to internal nodes for routing keys. Every routing key $K_{i}$ in an internal node also appears in some leaf — this duplication is what makes the "data always repeats in the leaves" statement true.

13.9.2 Worked Example: Building a B+ Tree for 1 to 10

The same values 1 through 10 are inserted into a B+ tree with $p = 4$ . Two conventions are used: left ordering for the median that rises (as in the B-tree), and a right bias — whenever a value appears in both a parent and a leaf, the matching value resides on the right side of the tree, so an equal key goes to the right child during splits.

Insert 1, 2, 3. The leaf accepts 1, 2, 3.

Insert 4. The leaf would hold 1, 2, 3, 4 — overflow. The median with left ordering is 2, which rises to the root. With the right bias, 2 stays in the right leaf. The root holds 2; the left leaf holds 1; the right leaf holds 2, 3, 4.

Insert 5. The leaf 2, 3, 4, 5 overflows. The median of 2, 3, 4, 5 with left ordering is 3, which rises. The root now holds 2, 3; the leaves hold 1; 2; and 3, 4, 5.

Insert 6. The leaf 3, 4, 5, 6 overflows. The median of 3, 4, 5, 6 with left ordering is 4, which rises. The root now holds 2, 3, 4; the leaves hold 1; 2; 3; and 4, 5, 6.

Insert 7. The leaf 4, 5, 6, 7 overflows. The median of 4, 5, 6, 7 with left ordering is 5, which rises. The root would hold 2, 3, 4, 5 — four keys, exceeding the limit of three, so the root itself splits: the median of 2, 3, 4, 5 is 3, which rises to a new root. The root holds 3; the left child holds 2; the right child holds 4, 5; and the leaves hold 1; 2; 3; 4; and 5, 6, 7. (The narration of this step in the session was garbled by a drawing-tool mishap — "I think I missed out" — and the spoken medians were inconsistent; the construction above is the one the stated rules produce, and it was re-verified line by line.)

Insert 8. The leaf 5, 6, 7, 8 overflows; 6 rises. The right child becomes 4, 5, 6 — three keys, which fits. The leaves now hold 1; 2; 3; 4; 5; and 6, 7, 8.

Insert 9. The leaf 6, 7, 8, 9 overflows; 7 rises. The child 4, 5, 6 becomes 4, 5, 6, 7 — overflow — so it splits with median 5 rising; the root becomes 3, 5. The leaves now hold 1; 2; 3; 4; 5; 6; and 7, 8, 9. (The session did not work out 9–10 step by step — "so on and so forth this discussion goes" — so they are reconstructed here from the stated rules and verified.)

Insert 10. The leaf 7, 8, 9, 10 overflows; 8 rises. The right child becomes 6, 7, 8 — three keys, which fits. Final tree: root 3, 5; children 2, 4, and 6, 7, 8; leaves 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8, 9, 10.

The final shape. Drawing only keys, with leaves at the bottom (record pointers and leaf-chain pointers omitted):

          3, 5
      /     |      \
    2       4       6, 7, 8
    |       |      /   |    |    \
    1       3     5    6    7    8, 9, 10
    2

Every leaf holds 1 to 3 keys; every internal node holds 1 to 3 routing keys; all leaves sit at the same depth — balanced. The essential invariants: data and record pointers exist only at the leaves; internal nodes carry only keys and block pointers; the leaf chain links every leaf to the next (3 → 4 → 5 → 6 → 7 → 8, 9, 10); and keys promoted to internal nodes (3, 5, and the 6, 7, 8 in the right child) remain in the leaves — which is why data "always repeats" in the leaves.

Pitfall — dropping the promoted key from the leaf. The most common B+ tree construction error: when the median rises, the student erases it from the leaf. In a B+ tree the promoted key stays in its leaf (right bias places it in the right leaf). Dropping it breaks the "data lives only at leaves" invariant — a record's only pointer would vanish.

Pitfall — forgetting that internal keys are routing keys. After the final insert, the internal node 6, 7, 8 contains no data — 6, 7, 8 route the search to leaves 6, 7, and 8, 9, 10 respectively. Writing data pointers beside them is B-tree behaviour, not B+ tree behaviour.

13.9.3 Range Queries with the Leaf Chain

Range queries are where the B+ tree shines, and this is the payoff for the whole design. Suppose the query asks for all student IDs between 3 and 300 — "find out all the names of the students whose ID numbers are between 3 and 300." In a B-tree, the answer requires walking into the tree, collecting some values, backing up, and walking down again — an awkward traversal across internal levels. In a B+ tree, the search descends once to the leaf where the range begins, and then walks straight along the leaf chain, because at the end of every leaf there is a pointer to the next block containing data. Records in the range are collected in one smooth pass. The professor's phrasing: "I will go to the leaf node and keep on traversing to the leaf node, because at the end of the leaf node there is a pointer to the next block which contains the data, and very quickly I can retrieve the data."

Visual intuition. Picture a horizontal chain of leaf blocks: leaf 1 → leaf 2 → leaf 3 → leaf 4 → leaf 5 → leaf 6 → leaf 7 → leaf 8, 9, 10, with an arrow from each leaf to the next. The y-axis is tree depth (root at top, leaves at bottom); the x-axis is key order. A range query lands on the chain at the left boundary of the range and glides right along the arrows until it passes the right boundary — each hop is one block access, and no internal node is ever revisited. Takeaway: range queries cost "find the start leaf + one access per leaf in the range," versus repeated backtracking in a B-tree.

13.9.4 Student Questions: Deletion, Practice, and Homework

Q: We only covered insertion in the B+ tree; we have not discussed deletion. Is that correct?

A: Yes, correct — deletion is difficult, and it was not covered in this session. The discussion will continue in the Tuesday evening session, on the deletion part of the B-tree and the B+ tree, along with practice.

Q: Can we expect these kinds of questions in the final exam?

A: Of course. As just mentioned, numericals will be there — I would be giving you something and you need to create a B-tree and a B+ tree. So I would definitely ask practical questions. Don't worry that it is only numerical and nothing more; the mid-semester paper already had certain theoretical questions and questions where you have to write SQL queries. But in practice and in interviews you need to be thoroughly convinced about the conceptual and application-based questions as well, so those are asked too.

Q: Is the material on B-tree and B+ tree insertion and deletion present in the textbook?

A: Definitely it is there, but I am not very happy with this textbook — it goes ahead with the names and is very complex. Playing with numbers is very easy: if you understood it, try it right away — take a few numbers and create a B-tree and B+ tree. If you want, you can send me an email or a WhatsApp message; I won't necessarily reply, but I will be sure that I am an accountable partner for you having done that. The other option: follow the worked examples shown in this session — mimic the same thing, two examples of B-tree and two of B+ tree are more than enough. And I will be coming back on Tuesday evening to do more practice; if you have studied those examples and been present today, by the Tuesday session you will find it very comfortable — confident enough to apply it.

The three confirmations to take away: (1) deletion was deliberately not covered — it is difficult, and it continues in the Tuesday evening session along with practice; (2) B-tree and B+ tree construction questions will definitely appear in the final exam — "I would be giving you something and you need to create a B-tree and a B+ tree" — alongside conceptual and application-based questions (the exam is mixed, not purely numerical); (3) the textbook's treatment exists but is dense ("very complex") — the professor's recommended practice is to invent your own small number set, build both trees, and check against the session's worked examples; two examples of each is "more than enough."

Exam note: the Tuesday session continues with B-tree and B+ tree deletion plus practice — plan study around that continuation. And expect an exam question that hands you values and a $p$ , and asks you to draw the B-tree and the B+ tree: keep the same left (or right) ordering throughout each construction.

The design, in one sentence: the B+ tree = B-tree rules + one architectural rule — data pointers only in leaves, internal keys are routing keys that repeat in leaves, leaves chained left-to-right. Insertion rises medians up the tree while keeping them in the leaves (right bias), and the final 1-to-10 tree has root 3, 5 over children 2, 4, 6, 7, 8.

Recap + bridge. The chain makes range queries cheap — which is exactly why every commercial engine defaults to the B+ tree, the subject of the next section.

13.10 Choosing an Index in Practice

13.10.1 Commercial Databases Default to B+ Trees

Q: Is the B+ tree, or the B-tree, the way any database system will practically store records? In MySQL, is it the same way?

A: Yes. MySQL and other storage engines use the B+ tree as an index. By default, all the commercial-level software uses the B+ tree. Even though we have discussed — and may discuss more — other indexes such as hash indexing or bitmap indexing, and there are multiple index types for the B-tree as well, commercial software uses the B+ tree. So when you say "create an index," it will create a B+ tree index.

CREATE INDEX in MySQL (and essentially every commercial engine — the professor named MySQL and Oracle; PostgreSQL, SQL Server, and InnoDB belong to the same family) creates a B+ tree by default. The B-tree, hash, and bitmap options exist, but the default is the B+ tree — a fact worth holding onto for both exams and interviews.

13.10.2 Scenario-Based Index Choice

Q: Which is the best indexing approach or mechanism in a database?

A: It depends upon the scenario. In the B+ tree you have to take more effort to create and maintain it — just like normalization. Even though you may say BCNF is better than 3NF, and 4NF better than BCNF, and 5NF (or PJNF) better than 4NF, the stricter and higher you go, the more effort it takes to create and preserve, and the reward-and-effort ratio becomes smaller. Similarly, the best indexing approach depends on the scenario.

The scenario map that was given:

B+ trees handle range queries best — "find everything between that range": all trains available throughout the day, all hotels available from this date to that date, the list of students who scored above 9 CGPA to give them a reward.
Bitmap indexes perform very, very well in very specific niche scenarios — specifically on conjunction (AND) and disjunction (OR) queries.
Multi-level indexes are great for storing or retrieving a specific value.
Hashing has its own advantages when a value must be fetched very quickly in a short manner.

Real-world: because real applications — trains, hotels, student records — run range queries constantly, commercial databases prefer B+ trees for that reason, in contrast to B-trees.

Formalize — the scenario map.

Index	Best scenario	Why	Example
B+ tree	Range queries	Leaf chain + routing keys	All hotels free between two dates
Bitmap	AND/OR (conjunction/disjunction) on few distinct values	Bit strings can be ANDed/ORed by hardware-fast bitwise ops	"Male AND senior AND department 5"
Multi-level index	Single-value lookups on stable data	Fixed levels, block anchors	Retrieve one specific record by key
Hashing	Exact-match lookups	One hash evaluation → one block access	Fetch the record with key 76543

The decision rule: there is no globally "best" index — the workload decides. Range-heavy workloads (the real world: trains, hotels, student lists) point to the B+ tree; AND/OR-heavy predicate workloads point to bitmap; exact single-value fetches can use hashing; stable data suits multi-level.

Professor analogy — index choice is like normalization choice. BCNF is better than 3NF, 4NF better than BCNF, 5NF (PJNF) better than 4NF — yet the stricter forms cost more effort to create and preserve, shrinking the reward-to-effort ratio. Indexes are the same: the "best" structure is the one whose benefits justify its maintenance cost for that scenario. No structure wins everywhere; each wins where the workload pays for it.

13.10.3 Third-Party Search Tools

Q: I have seen many third-party searching or indexing tools like Sphinx and Apache tools that also do some kind of indexing above the databases. Are the existing approaches in the database — like MySQL or Oracle — not enough to meet end requirements?

A: I would not be in a position to comment, since I have not used them. Since you have asked, I will look back into it and get back to you in the next class. At this point I cannot comment upon them.

The professor explicitly deferred: no comment on Sphinx or Apache-based indexers until the next class. What is settled is that such tools exist and build their own indexes on top of databases — a real-world reminder that application-level search (full-text, log search) often needs structures beyond what a DBMS's default B+ tree provides. No conclusion was reached in this session, so none is promised here.

Recap + bridge. There is no best index in the abstract — the workload decides. Commercial engines default to B+ trees (MySQL, Oracle), bitmap serves AND/OR niches, multi-level serves single-value lookups on stable data, hashing serves exact matches, and the choice mirrors the normalization effort-reward trade. Bridge: the final section locks all of this into a structural B-tree vs B+ tree comparison — the syllabus's explicit ask.

13.11 B-Trees vs B+ Trees: A Structural Comparison

Hook. One architectural rule — where the data pointers live — cascades into five differences, and each of the five is a legitimate exam question.

The syllabus calls for the structural differences between the B-tree and the B+ tree spelled out, and the two worked constructions of sections 13.8 and 13.9 give every difference a concrete shape. The single architectural rule that separates them — in a B-tree every node carries the data (key plus record pointer); in a B+ tree only the leaves carry the data — cascades into five consequences, each of which an exam question can target:

13.11.1 The Five Structural Differences

Where the record pointers live. In the B-tree, every key in every node has its record pointer — the internal node at height 3 already points at the data block. In the B+ tree, root and intermediate nodes hold only block pointers to the level below (the keys there are pure routing values), and the record pointers exist only in the leaves. The 13.8 construction showed record pointers beside 2, 4, 6, 8 at the root; the 13.9 construction showed the root holding only routing keys.
Key duplication. Because a promoted key must still guide a search down to the leaf that holds the data, every key that appears in a B+ tree internal node also appears in a leaf — the 13.9 splits kept the promoted median in the leaf ("data always repeats in the leaves"). In a B-tree each key occurs exactly once, at its own node.
The leaf chain. B+ tree leaves are linked left-to-right — each leaf ends with a pointer to the next leaf — which is what makes range queries a single pass along the chain. A B-tree has no leaf chain: a range query must walk down into the tree, collect values, backtrack up, and descend again — the awkward traversal of 13.9.3.
Search termination. A search in a B-tree can stop at an internal node when it finds the key there; a search in a B+ tree always descends to the leaves, because the key's record pointer lives only there. (The extra descent is the price of everything else.)
Fanout and height. Internal B+ tree nodes hold only routing keys and block pointers, so they can hold more keys per node than the corresponding B-tree node (whose internal slots carry record pointers); with $p = 4$ the B-tree node holds up to 3 key-pointer pairs, while the B+ tree's internal node can hold the same 3 keys but wastes nothing on data pointers — and because the B+ tree never stores data internally, more of the tree fits in fewer blocks. Higher fanout means a shorter tree for the same data, hence fewer block accesses from root to leaf — the reason the B+ tree wins on every measure that counts for a database index.

Property	B-tree	B+ tree
Data/record pointers in internal nodes	yes	no (routing keys only)
Key appears once, or repeated	once per key	key promoted to internal nodes is repeated in a leaf
Leaf chain for range scans	none	yes — leaves linked
Search can stop early at an internal node	yes	no — always descends to leaves
Fanout of internal nodes	smaller (data pointers occupy slots)	larger (keys only)
Range queries	in-order traversal with backtracking	descend once, walk the leaf chain

13.11.2 The Constructions Side by Side

Worked example — the two constructions side by side. Both trees received 1 through 10 with $p = 4$ and left ordering. B-tree (13.8): root 4; children (2) and (6, 8); leaves 1, 3, 5, 7, 9, 10 — every key appears exactly once, and the root itself points at records. B+ tree (13.9): root 3, 5; children 2, 4, 6, 7, 8; leaves 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8, 9, 10 — keys 3, 5 (and 6, 7, 8 in the right child) are routing copies whose originals live in leaves, and the leaves chain together. Range query "keys between 3 and 8": B-tree must descend, gather, backtrack, descend again; B+ tree descends once to leaf 3 and glides the chain to leaf 8, 9, 10.

Sense-check: the B+ tree has more leaves but equal height (both are two levels below their root, both balanced); its internal nodes hold pure routing keys, which is exactly why the same $p$ sustains more keys per block and shorter trees at scale.

The decision rule that commercial practice follows: the B+ tree is the default index in essentially every modern engine (MySQL/InnoDB, PostgreSQL, Oracle, SQL Server), because range queries dominate real workloads — the trains, hotels, and CGPA-range examples of section 13.10 — and the leaf chain plus higher fanout deliver them cheaply. The B-tree survives in the textbooks and in niches where keys are looked up individually and the tree must also serve as the data file itself. When a question says "compare B-tree and B+ tree," these five points in this order are the complete answer.

13.11.3 The Decision Rule in Practice

Pitfall — comparing on two differences only. A two-point answer ("B+ stores data only at leaves; B+ has a leaf chain") misses three examinable consequences: key duplication, search termination, and fanout/height. The five points in the fixed order of 13.11.1 — pointer location, duplication, chain, termination, fanout — are the complete answer.

Pitfall — assuming the B-tree is obsolete. The B-tree is not wrong, only different: it stops searches early, stores each key once, and serves as a primary file organization for small records. Commercial practice picks the B+ tree because real workloads are range-dominated, not because the B-tree is broken.

Recap + bridge. One rule (data only at the leaves) yields five differences: pointer location, key duplication, leaf chain, search termination, and fanout/height — and the last three are why commercial engines default to the B+ tree. Bridge: the two appendix sections that follow pull the exam guidance and the industry applications together.

Exam Guidance Summary

Exam note — the open-book strategy. The comprehensive exam is open book; knowing how to use the book's own index — locate a topic, jump to its pages — is a real exam skill that was shown in class.

Numericals carry the weight. Questions modeled on the three worked examples are to be expected: records per block, blocks for the file, index entries per block, index blocks, and block accesses with and without an index. Those who practiced get them; those who did not get exposed.
B-tree and B+ tree construction questions will appear. Expect to be given values and asked to draw a B-tree and a B+ tree with a given $p$ . Practice with small sets of random numbers, and keep left-ordering or right-ordering consistent throughout a tree.
Deletion comes next. B-tree and B+ tree deletion was not covered in this session and continues in the Tuesday evening session, along with practice.
The comprehensive exam concentrates on post-mid-semester material. "Most of the questions — the good weightage — will be on the topics after the mid-semester, since after mid-semester there is little time to evaluate you through projects or quizzes; having said that, there will be a few questions on normalization or other earlier topics as well. The higher weightage — significantly more, roughly 70 to 75 percent — will be on the course after the mid-semester." That figure is a ballpark, not a precise promise.
The exam is mixed. The mid-semester paper had theoretical questions and SQL-writing questions; the comprehensive exam can expect conceptual questions and application-based questions alongside the numericals. Interviews, similarly, test conceptual conviction, not just formula work.
Textbook pointers. The index chapter is Chapter 17 starting at page 602; Example 1 is at page 605, Example 2 at 606, and Example 3 at 609 in the seventh edition. Snapshots of Examples 2 and 3 were recommended.
Questions are welcome. No question is silly; asking during the session is encouraged, and typed questions are also taken.

Key Industry Applications

MySQL and other commercial storage engines use the B+ tree as the default index; issuing "create index" creates a B+ tree index. This is the standard answer for how real databases store and retrieve records.
Range-query industries run on B+ trees. Booking systems (trains available throughout the day), travel (hotels available between two dates), and institutional analytics (students above a CGPA threshold for rewards) all rely on range queries, which is why commercial databases prefer B+ trees over plain B-trees.
Bitmap indexes serve niche conjunction workloads. For AND/OR-heavy predicate queries, bitmap indexes outperform; they are scenario-specific, not universal.
Hashing remains the fast path for exact lookups. Previous sessions covered hashing for storing and fetching specific values quickly; it complements tree indexes.
Third-party search and indexing tools such as Sphinx and Apache-based tools build their own indexes on top of databases like MySQL or Oracle when the built-in indexes are not enough; their exact role was left for a follow-up.
Healthcare and campaign applications. A real project brief — storing anonymized healthcare records for patients — drives the design constraints: fast responses, high concurrency, correct answers, no spurious tuples.
Security hardening exists in industry. Cross-site scripting and injection prevention are separate specialties; a patent-filed scanner for cross-site scripting vulnerabilities and a project for the Data Science Council of India audited websites across companies and banking organizations. In this course the essential rule is simple: never let user-supplied data become executable SQL.
Book-style indexes. The physical index at the back of a textbook is itself a worked example of the indexing idea, and reading it is a legitimate study technique in an open-book setting.

DDA Lecture 13 notes · Indexing for Fast Retrieval: Primary Indexes, B-Trees, and B+ Trees

Database Design and Applications· postgraduate· 2026-08-06

Sections Breakdown

113.1 Weak Entities, Relational Conversion, and Functional Dependencies

Weak entities are converted into relations first (owner primary key plus distinguishing key form the composite key), and normalization operates on that relational schema; every normal-form decision depends on functional dependencies the designer writes down first, with the 2NF, 3NF, and BCNF decision ladder and the two-Nehas worked example.

213.2 The Application Big Picture: Where the Database Lives

A database is one component of an application hosted at a server with its own IP address; the designer's contract is a seven-point checklist for the healthcare-records scenario — speed, concurrency, correctness, constraints, common attributes, no spurious tuples, no rule violations — plus SQL injection and cross-site scripting.

313.3 The Retrieval Problem: Why Search Is Slow Without an Index

Real workloads grow into hundreds of thousands of records within days; records are moved in fixed-size blocks because of locality of reference, and each block access costs seek time plus transfer time — so raw search over 100,000 records is slow by default.

413.4 The Primary Index

A primary index is built on the ordering key of a sorted file: one <K(i), P(i)> entry per data block holding the anchor key value and block address; it is tiny, lives on secondary storage, speeds predicates, joins, and sorts on its attribute, and costs dynamic maintenance that must be repaid by retrieval speed.

513.5 Sparse, Dense, and Clustering Indexes

Dense indexes create one entry per value, sparse indexes skip entries and require sorted data, and clustering indexes create one entry per distinct value of a repeating non-key field — repetition defines clustering, not sparseness, and the axes of coverage and field type combine into the full taxonomy.

613.6 Worked Examples: What an Index Costs and Saves

Three numerical examples on an ordered file of 300,000 records with 4,096-byte blocks and 100-byte records: 40 records per block, 7,500 blocks, 13 binary-search accesses without an index, 372 index entries per block, and 3 + 1 = 4 accesses with a primary index; multi-level indexing cuts the index search itself.

713.7 Single-Level and Multi-Level Indexes: The Limits

Every insert or delete into a static multi-level index touches entries at every level, so these structures suit calm, stable files; ISAM is the classic static instance with fixed levels, an overflow area, and periodic reorganization; the alternative is the dynamic balanced tree — B means balanced, all leaves at the same level.

813.8 B-Trees: Balanced Tree Indexes

A B-tree node of order p holds at most p pointers, at most p-1 keys, and at least ceil(p/2)-1 keys, with all leaves at one level; inserting 1 through 10 with p = 4 and left ordering gives root 4 over (2) and (6, 8) — the only level gain at the root split on insert 10 — and left or right median ordering must stay consistent.

913.9 B+ Trees: Data Only at the Leaves

In a B+ tree, data and record pointers live only at the leaves; internal nodes carry routing keys, promoted keys stay in their leaf, and a leaf chain makes range queries a single pass; building 1 through 10 with p = 4 yields root 3, 5 over children 2, 4, and 6, 7, 8.

1013.10 Choosing an Index in Practice

MySQL and commercial engines default to B+ tree indexes; there is no best index in the abstract — B+ trees win on range queries, bitmap indexes on AND/OR workloads, multi-level indexes on stable single-value lookups, and hashing on exact matches, mirroring the normalization effort-reward trade.

1113.11 B-Trees vs B+ Trees: A Structural Comparison

The single rule that data pointers live only at leaves in a B+ tree cascades into five structural differences from the B-tree — pointer location, key duplication, leaf chain, search termination, and fanout/height — which is why commercial engines default to B+ trees.

12Exam Guidance Summary

Open-book exam strategy: numericals modeled on the three worked examples carry the weight, B-tree and B+ tree drawing questions will appear, deletion continues in the Tuesday session, and post-mid-semester material carries roughly 70 to 75 percent of the weightage.

13Key Industry Applications

Real-world use: MySQL and commercial engines default to B+ tree indexes; range-query industries (trains, hotels, student analytics) run on B+ trees; bitmap indexes serve AND/OR niches; hashing serves exact lookups; and anonymized healthcare records drive design constraints.

Postgraduate students of database design and applications

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Weak Entities, Relational Conversion, and Functional Dependencies

Must-know: Weak entities are converted to relations (owner key + partial key form the composite key) before any normalization; every normal-form decision needs functional dependencies written by the designer first.

$K_{W} = (K_{O}, c)$

⚠️ Top pitfall: Trying to normalize the ER diagram itself, or running the 3NF check before the 2NF check.

Self-check: Two children named Neha with identical name, dob and gender can be distinguished only when which attribute is added to the dependent relation?

Connects to: The application big picture, Choosing an index in practice

The Application Big Picture: Where the Database Lives

Must-know: The designer's seven-point checklist for the healthcare database: minimum response time, maximum concurrency, correct answers, respect constraints, common attributes between relations, no spurious tuples, no violations of application rules.

⚠️ Top pitfall: Building only the front end and ignoring the database contract; concatenating user input into SQL queries.

Self-check: List the seven requirements of the healthcare-records scenario.

Connects to: Weak entities and functional dependencies, The retrieval problem, The primary index

The Retrieval Problem: Why Search Is Slow Without an Index

Must-know: Records are fetched block by block (locality of reference); the costs are seek time and read/write time; a file of r records with blocking factor b occupies ceil(r/b) blocks.

$blocks = ⌈ \frac{r}{b} ⌉$

⚠️ Top pitfall: Thinking of disk as memory; a block access costs the same whether one record or forty are wanted from that block.

Self-check: Why is data fetched in blocks rather than record by record?

Connects to: The application big picture, The primary index, Worked examples of index cost and savings

The Primary Index

Must-know: A primary index stores one key–pointer entry per data block on a sorted key field; SQL's CREATE INDEX leaves the index type (B-tree, B+ tree, hash, bitmap) to the database software.

$⟨ K (i), P (i)⟩$

⚠️ Top pitfall: Thinking the index stores the data records or has one entry per record; expecting an index to speed queries on other attributes.

Self-check: How many index entries does a primary index have for a file of 10,000 blocks?

Connects to: Sparse, dense, and clustering indexes, Worked examples of index cost and savings, Choosing an index in practice

Sparse, Dense, and Clustering Indexes

Must-know: Dense = entry for every value; sparse = some entries skipped (needs sorted order); clustering = one entry per distinct value of a repeating non-key field. The primary index is sparse.

⚠️ Top pitfall: Equating dense/sparse with repeating/unrepeated values; repetition defines clustering instead.

Self-check: The hostel example: how many index entries does a clustering index on hostel names have for 1,000 students in 8 hostels?

Connects to: The primary index, Worked examples of index cost and savings, Single-level and multi-level indexes

Worked Examples: What an Index Costs and Saves

Must-know: records per block = floor(4096/100) = 40; blocks = 300,000/40 = 7,500; binary search = ceil(log2 7,500) = 13; index entries per block = floor(4096/11) = 372; 1,000 entries in ceil(1000/372) = 3 index blocks; accesses = 3 + 1 = 4.

$accesses without index = ⌈ lo g_{2} (7, 500)⌉ = 13, with index = 3 + 1 = 4$

⚠️ Top pitfall: Mixing up floor and ceiling (a 40.96-byte record does not fit — floor it); forgetting the +1 data-block access after the index search.

Self-check: With 300,000 records of 100 bytes and 4,096-byte blocks, how many records fit per block and how many blocks does the file need?

Connects to: The primary index, Sparse, dense, and clustering indexes, Single-level and multi-level indexes

Single-Level and Multi-Level Indexes: The Limits

Must-know: B means balanced tree; in a B-tree all leaves sit at the same level (stricter than AVL's ±1). ISAM = static multi-level index: sorted data, fixed levels, overflow area for inserts, reorganization to recover. Multi-level indexes are for stable databases.

⚠️ Top pitfall: Writing ISAM's exam answer too thin; forgetting the overflow area and reorganization; confusing AVL's ±1 balance with the B-tree's equal-level rule.

Self-check: Why does inserting a record into a two-level index require updates at multiple levels?

Connects to: Worked examples of index cost and savings, B-trees, B+ trees

B-Trees: Balanced Tree Indexes

Must-know: B-tree of order p: max p pointers, max p-1 keys, min ceil(p/2)-1 keys per node, all leaves at the same level. For p=4: max 3 keys, min 1 key. Construction for 1..10 with left ordering: root 4, children (2) and (6,8), leaves 1 | 3 | 5 | 7 | 9,10.

$max keys = p - 1 = 3, min keys = ⌈ p /2 ⌉ - 1 = 1$

⚠️ Top pitfall: Mixing left and right median ordering across splits; forgetting the root split at insert 10 (median 4 of 2,4,6,8 rises).

Self-check: For p = 4, what is the minimum and maximum number of keys a B-tree node may hold?

Connects to: Single-level and multi-level indexes, B+ trees, B-tree versus B+ tree comparison

B+ Trees: Data Only at the Leaves

Must-know: B+ tree: data pointers only at leaves; promoted median stays in the leaf (right bias); leaf chain for range queries. Construction 1..10, p=4: root 3,5; children 2, 4, 6,7,8; leaves 1|2|3|4|5|6|7|8,9,10. Deletion not covered — Tuesday session.

⚠️ Top pitfall: Erasing the promoted key from its leaf during a split; writing data pointers beside internal routing keys.

Self-check: Why does a range query need only one descent in a B+ tree?

Connects to: B-trees, Choosing an index in practice, B-tree versus B+ tree comparison

Choosing an Index in Practice

Must-know: MySQL and commercial engines default to B+ trees; CREATE INDEX creates a B+ tree index. Scenario map: B+ tree for ranges, bitmap for AND/OR, multi-level for single values on stable data, hashing for exact matches.

⚠️ Top pitfall: Claiming one index type is universally best; ignoring the effort-reward trade of stricter structures.

Self-check: Which index type should a booking system use for 'all hotels available between two dates'?

Connects to: The primary index, B+ trees, B-tree versus B+ tree comparison

B-Trees vs B+ Trees: A Structural Comparison

Must-know: Five differences: (1) record pointers only in leaves for B+; (2) promoted keys repeat in B+ leaves; (3) B+ has a leaf chain; (4) B+ search always descends to leaves; (5) B+ internal nodes have larger fanout, shorter trees.

⚠️ Top pitfall: Answering 'compare B-tree and B+ tree' with only two differences; forgetting the leaf chain and fanout consequences.

Self-check: Why does a B+ tree have a shorter height than a B-tree for the same data?

Connects to: B-trees, B+ trees, Choosing an index in practice

Exam Guidance Summary

Must-know: Numericals (records per block, blocks, index entries per block, block accesses) are the exam discriminator in an open-book setting; expect B-tree and B+ tree drawing questions with a given p.

⚠️ Top pitfall: Relying on open-book lookup instead of practicing numericals.

Self-check: What is the approximate weightage of post-mid-semester topics in the comprehensive exam?

Connects to: Worked examples of index cost and savings, B-trees, B+ trees

Key Industry Applications

Must-know: CREATE INDEX in commercial engines (MySQL and others) creates a B+ tree index by default; range queries dominate real workloads.

Self-check: Why do booking systems prefer B+ trees over plain B-trees?

Connects to: Choosing an index in practice, B-tree versus B+ tree comparison

Previous LectureLecture 12 · The Evolution of Database Systems: Indexing, Transactions, and Concurrency

Next LectureLecture 14 · B+ Trees, Transactions, and ACID

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

13.1 Weak Entities, Relational Conversion, and Functional Dependencies

13.1.1 The Question: Can Weak Entities Be Normalized?

13.1.2 Converting a Weak Entity into a Relation

13.1.3 Defining Functional Dependencies First

13.1.4 The Second and Third Normal Form Rules

13.1.5 Arbitrary Keys and Surrogate Identifiers

13.2 The Application Big Picture: Where the Database Lives

13.2.1 Client, Application, and Database

13.2.2 The Healthcare Records Scenario

13.2.3 Security: Injection and Cross-Site Scripting

13.3 The Retrieval Problem: Why Search Is Slow Without an Index

13.3.1 The Scale of Real Workloads

13.3.2 Blocks, Seek Time, and Locality of Reference

13.3.3 The Index as the Answer

13.4 The Primary Index

13.4.1 Ordering Field and Key

13.4.2 The Anatomy of an Index Entry

13.4.3 Student Questions: SQL Indexes, Pointers, and Index Tables

13.4.4 Indexes and Joins

13.4.5 Effort and Reward

13.5 Sparse, Dense, and Clustering Indexes

13.5.1 The Three Flavors

13.5.2 The Combinations

13.5.3 Where the Index Lives

13.5.4 Student Questions and a Deferred Promise

13.6 Worked Examples: What an Index Costs and Saves

13.6.1 The Setup: Ordered File, 300,000 Records

13.6.2 Example 1: Binary Search Without an Index

13.6.3 Example 2: With a Primary Index

13.6.4 Example 3: The Multi-Level Index

13.6.5 Reading the Textbook's Index

13.6.6 Exam Notes: Numericals in an Open-Book Exam

13.7 Single-Level and Multi-Level Indexes: The Limits

13.7.1 The Insertion and Deletion Pain

13.7.2 When Multi-Level Indexes Work Well

13.7.3 Trees: The Next Step

13.7.4 What Does the "B" Stand For?

13.7.5 ISAM: The Indexed Sequential Access Method

13.8 B-Trees: Balanced Tree Indexes

13.8.1 The Structure of a B-Tree Node

13.8.2 Worked Example: Building a B-Tree for 1 to 10

13.8.3 The Final B-Tree and Its Properties

13.8.4 Left Ordering versus Right Ordering

13.9 B+ Trees: Data Only at the Leaves

13.9.1 The Difference Between B-Tree and B+ Tree

13.9.2 Worked Example: Building a B+ Tree for 1 to 10

13.9.3 Range Queries with the Leaf Chain

13.9.4 Student Questions: Deletion, Practice, and Homework

13.10 Choosing an Index in Practice

13.10.1 Commercial Databases Default to B+ Trees

13.10.2 Scenario-Based Index Choice

13.10.3 Third-Party Search Tools

13.11 B-Trees vs B+ Trees: A Structural Comparison

13.11.1 The Five Structural Differences

13.11.2 The Constructions Side by Side

13.11.3 The Decision Rule in Practice

Exam Guidance Summary

Key Industry Applications

DDA Lecture 13 notes · Indexing for Fast Retrieval: Primary Indexes, B-Trees, and B+ Trees

Sections Breakdown

Exam Revision Notes

Weak Entities, Relational Conversion, and Functional Dependencies

The Application Big Picture: Where the Database Lives

The Retrieval Problem: Why Search Is Slow Without an Index

The Primary Index

Sparse, Dense, and Clustering Indexes

Worked Examples: What an Index Costs and Saves

Single-Level and Multi-Level Indexes: The Limits

B-Trees: Balanced Tree Indexes

B+ Trees: Data Only at the Leaves

Choosing an Index in Practice

B-Trees vs B+ Trees: A Structural Comparison

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat