—

Database Design and Applications

Hashing, Extendible Hashing, and the HealthTrack Assignment

Published: 2026-08-06

Level: postgraduate

Audience: Postgraduate students of database design and applications

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Normalization, functional dependencies, and the normal forms — covered in Lecture 4 (Normalization: Turning Instinct into Certainty)
BCNF guarantees and the decomposition method — covered in Lecture 5 (Database Normalization: Closure, Minimal Cover, and the 3NF Synthesis Algorithm)
Candidate keys and normal-form checks — covered in Lecture 9 (Candidate Keys, ER-to-Relational Mapping, and Normalization Revision)
Physical storage: volatile and non-volatile memory, the magnetic disk, and the buffer manager — covered in Lecture 10 (Storage, File Organization, and Indexing)
Indexing: search keys, ordered indexes, and hash indexes — covered in Lecture 10 (Storage, File Organization, and Indexing)
The project assignment brief — covered in Lecture 10 (Storage, File Organization, and Indexing)

11.1 Quiz 2 Review: Decomposition, Dependency Preservation, and Lossless Join

Hook: A quiz question about decomposition had no single right answer — two options both earned full marks. Before you can judge any statement like "decomposition into 3NF or BCNF is dependency preserving," you need to know exactly what the two properties mean, why normalization demands them, and which normal form promises which one. This section builds that foundation, because the same reasoning reappears in the exam and in the HealthTrack assignment.

11.1.1 The Question and Its Four Options

The review opened with a question from quiz 2 about decomposition in the context of normalization. The question offered four options, and the discussion walked them through one at a time, judging each against the definitions.

Worked example — judging the four quiz options:

Option	Claim	Verdict	Why
A	Every decomposition increases data redundancy to maintain data integrity	Wrong	Normalization exists precisely to reduce redundancy. Decomposition is the tool that removes it.
B	Decomposition can only achieve first normal form without touching the original functional dependencies	Wrong	Decomposition is how we move through every normal form — 2NF, 3NF, up to BCNF.
C	Decomposition into 3NF or BCNF may not always be dependency preserving, but it guarantees lossless join	Half right, half wrong	The sentence mixes two normal forms with different guarantees (see below).
D	The most appropriate answer of the set	Accepted with C	It reflects the same conclusion after careful reading of the assumptions.

The conclusion after the discussion: both option C and option D deserve full marks. Option C is not a clean true-or-false statement — the truth of "may not always be dependency preserving" depends entirely on which normal form you decompose into and on the assumption that the decomposition was done the textbook way. The marks for this question will be updated.

Exam note: both option C and option D were accepted as the most appropriate answers for this quiz question, and the quiz 2 marks are being updated. The lesson for any exam statement about decomposition: read it twice — once for which normal form it names, once for which decomposition method it silently assumes.

11.1.2 What Dependency Preservation and Lossless Join Mean and Why We Need Them

The normalization story starts with a goal: turn a relational schema into a good relational schema. We already had an ER diagram, and we had already converted it into a relational schema, but that schema was not good enough — it might lack proper semantics, carry a lot of redundancy or anomalies, contain many null entries, and even produce spurious tuples when queries join relations. Because we do not want redundancy — we want certainty when we take action on data — we keep designing better schemas as we move from first normal form to second normal form to third normal form and on to BCNF.

Why a functional dependency implies redundancy. A functional dependency (an integrity constraint that fixes the value of one attribute set given another), written $X \to Y$ , says: whenever the attribute set $X$ repeats, the attribute set $Y$ repeats too. The moment the same $X$ value appears in two rows, both rows must carry the same $Y$ value — so at least at the level of $Y$ , repetition exists inside the relation. Every step of normalization is literally redundancy reduction: each normal form removes one class of this repetition.

Lossless join is the property that protects the meaning of the data when the split relation is rebuilt. When we join two relations back together to answer a query, if the common attribute on which we join is not a key in at least one of the relations, the join can manufacture data that never existed.

Worked example — how spurious tuples appear. Suppose the original data is:

emp_id	dept_id	project
101	D1	P1
102	D1	P2

Someone decomposes it into two relations on the non-key attribute dept_id:

R1(emp_id, dept_id) = {(101, D1), (102, D1)}
R2(dept_id, project) = {(D1, P1), (D1, P2)}

Joining R1 and R2 on dept_id multiplies every combination: (101, D1, P1), (101, D1, P2), (102, D1, P1), (102, D1, P2). Two of these — (101, D1, P2) and (102, D1, P1) — never existed in the original data. They are spurious tuples (fake rows created by the join, not by reality). More data exists, yet certainty drops.

Sense-check: the join gave 4 rows from 2 + 2 rows of input, so the join must have invented rows. A lossless join would have produced exactly the original 2 rows.

That is exactly why lossless join is a required property: a lossless-join decomposition creates no spurious tuples, no extra entries, and keeps the answer to "is this exactly what exists?" trustworthy. From 1NF to 2NF to 3NF to BCNF, the lossless-join property always needs to be ensured.

Dependency preservation. A functional dependency is a constraint on the data: an implicit relationship between attributes. If we decompose and the attributes of the dependency end up in separate relations, the information about that constraint can be lost — we might no longer be able to determine $X \to Y$ even when all the dependencies are written down together. A decomposition is dependency preserving (keeps every functional dependency enforceable within some single relation of the decomposition) when no dependency is scattered across relations this way. For a schema that originally carried that constraint, losing it is not a healthy sign.

Scope — which normal form promises which property:

	1NF → 2NF → 3NF	3NF → BCNF
Lossless join	Always required	Always required (when decomposed the proper way)
Dependency preservation	Always required — every functional dependency is kept	Acceptable to miss some dependencies

BCNF is a very strict level of decomposition with very little redundancy. At the cost of reducing redundancy, it is okay to compromise on some functional dependencies — 3NF exists precisely as the normal form that keeps every dependency while accepting the small amount of redundancy BCNF removes. What BCNF still demands — when the decomposition is done the proper way — is a lossless join.

The same point resolves the quiz confusion about BCNF. There are decompositions into BCNF that are lossless, and there are decompositions into BCNF that are not, depending on how you decompose. The textbook example — a chain of dependencies $A \to B$ , $B \to C$ , $C \to D$ — admits more than one option.

Worked example — the chain $A \to B$ , $B \to C$ , $C \to D$ , two decompositions, two outcomes.

The proper decomposition (following the algorithm): separate each violating dependency into its own relation.

R1(A, B) with $A \to B$ — key $A$ , BCNF.
R2(B, C) with $B \to C$ — key $B$ , BCNF.
R3(C, D) with $C \to D$ — key $C$ , BCNF.

Lossless check (rule: a two-way decomposition is lossless when the shared attribute set is a key of at least one side): R1 ∩ R2 = {B}, and $B \to C$ makes B a key of R2 — lossless. Then (R1 ⋈ R2) ∩ R3 = {C}, and $C \to D$ makes C a key of R3 — lossless overall. Dependency check: $A \to B$ lives in R1, $B \to C$ in R2, $C \to D$ in R3 — every dependency preserved. This decomposition is lossless and dependency preserving.

An ad hoc decomposition: R1(A, C, D) and R2(B, C). Both relations are in BCNF — the only nontrivial dependencies on R1 are $A \to C$ and $A \to D$ with key A, and R2 has key B. But:

Lossless check fails: R1 ∩ R2 = {C}. Is C a key of R1(A, C, D)? No — the key is A. Is C a key of R2(B, C)? No — the key is B. C is a key of neither, so the join can manufacture spurious tuples.
Dependency check fails: $A \to B$ no longer fits in any single relation — A lives in R1, B lives in R2, and no relation contains both.

So both decompositions are in BCNF, but one is lossless and dependency preserving while the other is neither. The normal form alone says nothing; the method decides.

Sense-check: BCNF limits redundancy, not the method of decomposition. The same schema, decomposed two different ways, gives two different guarantee profiles — exactly why the quiz statement needed care.

So the statement "BCNF guarantees lossless join" needs care: if you follow the proper way, BCNF does guarantee it, because lossless join is part of how you are supposed to do it — but a decomposition you arrive at by some other path can be in BCNF and still fail the lossless-join test.

11.1.3 Following the Algorithm versus Decomposing by Hand

Moving from 1NF to 2NF is not unique: there is more than one way to decompose, depending on how you do it.

The algorithm, step by step. If $X \to Y$ causes the normal-form violation:

Create a separate relation $X Y$ (both sides of the violating dependency together).
Remove $Y$ from the original relation.
Keep $X$ in the original relation.

If you follow the steps one by one, as the textbook expects, you always reach 1NF → 2NF → 3NF with dependency preservation intact.

But people sometimes decompose in a different, ad hoc way — removing the 2NF violation or the transitive dependency without actually following the algorithm — and then claim the schema is still in 2NF or 3NF because no violation is visible. That is when dependencies can slip away: the schema looks correct, yet some functional dependency is amiss.

Pitfalls:

Judging a decomposition only by the visible normal form. A schema in 3NF with a lost dependency is still in 3NF — the loss is invisible until you test every original functional dependency.
Assuming "BCNF guarantees lossless join" is unconditional. It holds only when the decomposition method builds losslessness in; other paths to BCNF can fail it.
Testing lossless join with your eyes instead of the rule. The shared attribute must be a key of at least one side — if it is a key of neither, expect spurious tuples.
Believing 3NF and BCNF make the same promises. 3NF always preserves dependencies; BCNF may sacrifice some to eliminate redundancy.

The same logic carries into the quiz question: statements like "decomposition into 2NF always results in a lossless, dependency-preserving design" rest on the assumption that the textbook-level method was used. Under that assumption the statement holds; without it, variations are possible. This is why the question had a lot of assumptions baked in, and why both option C and option D were accepted as the most appropriate answers.

11.1.4 Student Questions and Answers

Q: The decomposition rule — lossless join and dependency preserving — does it apply to every decomposition, or only from a specific normal form to a specific normal form?

A: First understand what the two properties mean and why we need them; then the "when" question answers itself. We normalize because we want a good relational schema: less redundancy, no anomalies, no nulls, no spurious tuples. A functional dependency means whenever $X$ repeats, $Y$ repeats, so some redundancy lives inside the relation; each normal form step reduces it. Lossless join is what stops the join from creating extra tuples: when the common attribute of two relations is not a key, the join can multiply entries and give more data but less certainty. Dependency preservation keeps the implicit constraint between attributes alive. From 1NF to 2NF to 3NF both properties must hold. From 3NF to BCNF, losing some functional dependencies is allowed, because BCNF buys very low redundancy at that cost — but lossless join still has to be ensured when you decompose the proper way.

Q: Will there be any impact on functional dependency preservation when we move from 1NF to 2NF? Is there a chance of compromising on one of these properties between 1NF and 2NF?

A: An important question, and the answer depends on how you decompose. There is not only one way from 1NF to 2NF. If you follow the algorithm — for $X \to Y$ , make a separate relation $X Y$ , remove $Y$ , keep $X$ in the original — then from 1NF to 2NF to 3NF the dependencies are always preserved. But an ad hoc decomposition that only removes violations without following the algorithm can leave dependencies lost even though the schema is in 3NF — no violation is visible, yet something is amiss.

Q: So 3NF will always be dependency preserving, correct?

A: Yes — 3NF is always dependency preserving and always lossless join, assuming you decompose properly. Look at the quiz option again: "decomposition into 3NF or BCNF may not always be dependency preserving." For 3NF that sentence is not right, because 3NF should always preserve dependencies. For BCNF it is right, because BCNF may not always be dependency preserving. So the statement as a whole mixes two normal forms with different guarantees, which is why the question needed careful reading — and why both options C and D were accepted.

Q: You said decomposition into BCNF is always lossless join — is that right, or does it depend on how you decompose?

A: Be careful here. Lossless join depends on how you decompose. In BCNF there can be more than one way to decompose — for example a chain like $A \to B$ , $B \to C$ , $C \to D$ . One option preserves lossless join; another option may not. So some decompositions that end up in BCNF are not lossless join at all. If you are doing it the proper way, BCNF will guarantee lossless join because ensuring it is part of the method — but you cannot blindly say every BCNF decomposition is lossless.

Recap: A functional dependency means repetition; normalization means removing that repetition step by step. Every decomposition must be checked for two properties — lossless join (no spurious tuples, always required, all the way to BCNF) and dependency preservation (the constraints stay enforceable; required through 3NF, relaxable at BCNF). The guarantee any normal form gives is only as strong as the method that produced it — the algorithm protects both properties, ad hoc decomposition protects neither. This is the lens you will use on the quiz, the exam, and the HealthTrack assignment when you convert your relational model into 3NF.

In practice, these two properties are what make normalized schemas safe for real systems: a hospital or bank cannot query a patient's or account's history and silently receive rows that never existed, and it cannot lose a business rule like "one employee belongs to one department" during redesign. Dependency preservation keeps the rule enforceable by the database; lossless join keeps the answers trustworthy. Both are design contracts you check before shipping a schema — the same check you will perform on the HealthTrack relational model.

11.2 Storage Fundamentals: Why Database Access Is Disk-Bound

Hook: Your processor can perform a calculation in nanoseconds, yet a query on a million-row table can still take seconds. The gap is not the processor — it is the hard disk. Almost every database design decision in this course (hashing, indexing, buffer management) exists because data lives on a slow disk and the processor only ever sees fast main memory.

11.2.1 The Two Spaces: Hard Disk and Main Memory

Before any hashing discussion makes sense, you need the storage picture. The database lives on the hard disk, in a separate space from the main memory. In the von Neumann architecture (the classic computer design in which the processor fetches instructions and data from memory, executes, and stores results back) there is a processor, and close to the processor there is the random access memory (RAM) — the memory in which the processor can make algorithmic decisions very fast.

The two spaces, side by side:

	Hard disk	Main memory (RAM)
Size	Large — holds all the data	Small — a fraction of the disk
Speed	Slow — milliseconds per access	Fast — nanoseconds per access
Cost per byte	Cheap	Expensive
What lives there	The whole database	Only the data currently in use

The gap matters at every step: a disk access takes roughly a million times longer than a memory access. That single ratio is why the field spends its energy minimizing how many disk transfers happen, not how many instructions run.

The large data resides on the hard disk, and the disk is physical: there are platters (the round magnetic plates that store data), and within the platters there are tracks (concentric rings on a platter surface), and within the tracks there are sectors (the segments of a track that hold a fixed amount of data). For every operation — insertion, deletion, update, or a plain read — the system must know which sector and which track the data lives in, pull it from the hard disk into the main memory, and only then can the processor act on it and return the result to the screen.

The transfer happens block by block: a block (the smallest unit of disk data transferred in one read; also called a page) is pulled from the hard disk into main memory at a time, and that is how the work gets done. The processor never reads one byte from disk; it reads whole blocks. Respecting that there are two spaces — a slow, large disk and a fast, small main memory — is the motivation for everything that follows.

Pitfalls:

Thinking the processor "sees" the disk. It does not — data must first be copied into main memory, block by block, before any instruction can touch it.
Counting work in instructions. Database cost is counted in block transfers; an algorithm that computes a lot in memory but reads few blocks can beat one that reads many blocks.
Ignoring the block boundary. Two records you want together should share one block; if they are scattered across two blocks, you pay two transfers.

11.2.2 The Join Example and Block-by-Block Transfer

A concrete example makes the cost visible.

Worked example — the mid-semester query, step by step. Suppose we want to find the students who scored above 15 marks in the mid-semester, and for each of them report the email id. The data lives in two tables:

Student(id, name, email) — student data including the email id.
Marks(id, mid_sem_marks) — the id number and the marks.

Step 1 — read: both tables sit on disk; not even the first comparison can happen until their blocks are pulled into main memory.

Step 2 — transfer: suppose Student occupies 500 blocks and Marks occupies 100 blocks. A naive approach fetches every pair of blocks — that is 500 × 100 = 50,000 block transfers, each one a disk access.

Step 3 — join and filter: inside memory, for each Student row the processor matches the id in Marks, keeps only rows with mid_sem_marks > 15, and copies out the matching email id.

Step 4 — report: the result rows are returned to the screen.

Sense-check: the query itself is tiny — a handful of students with emails — but the answer cost 50,000 disk transfers because the two tables were fetched with no scheme for finding the needed blocks. If the system could go directly to the blocks that hold the students above 15 marks, the same answer would cost a handful of transfers. That saving is exactly what hashing and indexing exist to deliver.

If you visualize that — the constant shuttling of blocks between disk and memory, with the processor only ever seeing main memory — you start to appreciate what computer scientists and entrepreneurs had to build to give us what we see on screen today. The science here is an appreciation that the same pattern shows up in database systems work and in ordinary problem solving: whenever a scarce, slow resource sits between you and your goal, the quality of your scheme for reaching it decides everything.

Visual intuition: picture two boxes. The small fast box (main memory) sits beside the processor; the big slow box (disk) is far away, and between them moves a conveyor that can carry exactly one block at a time. Every query is a line of work waiting on that conveyor: the processor idles whenever the conveyor is slow. The landmark to notice is the conveyor itself — the number of block transfers is the query's real price tag. One-sentence takeaway: making the conveyor shorter (fewer transfers) matters more than making the processor faster.

11.2.3 Organizing Like a Filing System

Think about your own computer. When you want a particular presentation file, you do not scan every file on the machine. You have arranged things so that you can get there fast: on the D drive you wrote out all the folders related to your master's program, each course has its own folder, and inside a course folder there is a folder for presentations and folders for other material. You go straight to the right folder and retrieve the file.

Intuition — the professor's filing-system analogy: the hard disk is your D drive. You did not memorize the disk address of every file; you built an ordering (folders inside folders) that lets you compute where the thing you want should be and go there in a few steps. The physical disk is the same story: all the data is stored in some manner, but we still need a scheme for quickly working out which block holds the data we want, so we can pull exactly that block into memory. That need for organization — an order that makes fast retrieval possible — is the reason hashing and indexing exist. Where the analogy breaks: a folder name tells you a place, but disk blocks have no friendly names — so the scheme has to be computed from the data value itself.

Recap + bridge: The database lives on a slow, large disk; the processor only ever works on a fast, small main memory; and the only bridge between them is block-by-block transfer. Every query's cost is the number of blocks it moves. That is why the next topic exists: the data is already somewhere on the disk — hashing and indexing are the two techniques for answering, quickly, which block that is.

This pattern is not an academic curiosity. Real database systems keep a buffer pool — a portion of main memory holding recently used blocks — precisely to reduce the shuttling described here, and every storage engine's design report quotes its cost in disk I/Os. The same two-space logic applies to web applications: the fastest way to speed up a slow endpoint is often to find the one query that moves too many blocks and give it an index. When you later choose hash-based versus normal indexing for the HealthTrack assignment, you are answering this section's question: which scheme gets the application's queries to the right blocks fastest?

11.3 Hashing and Indexing: Two Techniques for Finding the Block

Hook: Every time you press Enter on a query, the database has to answer one question first: which block is my data in? Two families of techniques answer it — indexing and hashing — and they answer it in such different styles that each is a poor substitute for the other in exactly the cases where the other shines.

11.3.1 The Shared Purpose

The major purpose of both hashing and indexing is the same: the data is on the hard disk, it must be pulled into main memory to produce results, and someone has to find out where it actually is.

The one question both techniques answer. The file occupies some number of blocks on disk, numbered from the first to the last. Given a record's key value, the question is: which block number holds this record? Hashing and indexing are both techniques for answering that question quickly — for finding out at what particular block number the data resides. Everything else (the directory, the hash function, the tree) is a detail attached to that single purpose. If the purpose is clear in your head, the techniques become far more interesting. The same constraints and requirements can appear in other courses, and the same techniques can be applied in real life beyond computer science — whenever the same problem shows up, the same solution can be reused.

11.3.2 Indexing: The Book-Index Model

You already know an index from everyday life: the index at the back of a book. Open the last pages of a book and you find terms — "database", "transaction" — each with a page number next to it. You look up the keyword topic and it tells you which page holds it.

Intuition — the professor's book-index analogy: a book index maps a keyword topic to a page number. A database index works the same way: it is a structure that maps a key value to a location, and you reach the data through that mapping. You do not read the whole book to find "transaction" — you open the index, read the page number, and go there. The database does the same: one lookup into the structure, one jump to the block. Where the analogy stretches: a book index is static (pages never move), while a database index must be updated on every insertion and deletion — which is exactly where its maintenance cost comes from.

The professor notes that indexing can handle a lot of data — files with many blocks — and scales nicely, especially in B+ tree style indexing (a balanced tree structure whose entries are kept in sorted order, described later in the course), which is a very clean way to search. One cost: an index may take two, three, or four tries to get you to the data, because the lookup goes through the structure rather than straight to the block.

11.3.3 Hashing: Direct Access

Hashing takes the opposite route: instead of walking through a structure, a hash function computes the location directly from the key value.

Direct access. The basic promise of hashing is that in the order of one or two steps you are there — hashing gives you direct access to the block. If you only want to retrieve one specific thing (an exact equality match, like "give me the record with id 24"), hashing works very nicely. The strength of indexing is different: it scales to large files and it shines for range queries (queries that ask for every value in an interval, like "all students with marks between 15 and 20"). Neither is universally better; which one you use depends on what you are retrieving — and the detail of that trade-off is exactly what the rest of the topic covers.

Comparison — hashing versus indexing, when to pick which:

Dimension	Hashing	Indexing
How you get to the block	A function computes the address directly	Walk through a structure (e.g., a B+ tree)
Steps to the data	One or two	Two, three, or four
Perfect for	Exact-match retrieval of one record	Large files, sorted access, range queries
Scaling	Requires dynamic schemes as the file grows	Scales cleanly, B+ trees especially
Cost of upkeep	The hash scheme itself	Storage, processing power, and energy to create and maintain

When to pick which: pick hashing when your queries ask for one specific record by its key; pick indexing when your data is large, your queries ask for ranges, or you need ordered access.

11.3.4 Student Questions and Answers

Q: What is the difference between indexing and hashing?

A: Both do the same job — help us find data faster and retrieve it faster — and the difference is the way they do it. Indexing is like the index at the back of a book: you specify the keyword topic, and the index tells you the page number, so you retrieve it from there. Hashing is also trying to get to the data very fast, but it does it with an entire algorithm — a function computes the address. By hashing you get there in one or two steps; by indexing you may need two, three, or four tries. The advantage of indexing is that it can carry a lot of data in a scalable manner — with B+ tree indexing it is a very clean way to search over ranges, so range queries work nicely. Hashing is best when you just want to retrieve one thing.

Q: With indexing you still have to land somewhere and scan, but the scanning is quick — you eliminate what you do not need, though there is still a small amount of search. With hashing you get direct access. Is that the right picture?

A: Exactly right. That is very nicely summarized — hashing gets you direct access, while indexing involves limited, fast scanning. The index narrows the search to a tiny region and then scans within it; hashing skips the narrowing entirely.

Q: Is indexing using a kind of data structure that keeps key-value pairs, whereas a hashing function gives a key so we get a value that we can use directly as a reference to something?

A: Right — bang on. When we discuss indexing in detail you will see exactly why the key-value picture is correct. (For anyone who has not met key-value data structures yet, that idea — a value reachable through a key — is all you need to hold onto for now.) In both families the key is the search value and the value is a location: a directory slot for hashing, a tree path for indexing.

Q: Indexing impacts the performance of insertion and updation-related queries. Does hashing work in a similar manner?

A: Yes — the agenda items for both are the same. Both are meant to find the block in which the data resides fastest; after that we may search, insert, update, or do whatever we want. So both enhance the performance of searching, insertion, and updation. And there is a balance to strike: creating and maintaining an index costs storage space, processing power, and energy — insertion, updation, and maintenance of the index itself. You cannot index everything for free; you decide how many indexes to create, and once maintained, they improve performance. Without them you have to go linearly through the blocks to find the data.

Recap + bridge: Hashing and indexing serve one shared purpose — locating the block that holds a record — and differ only in how they get there: hashing computes the address in one or two steps (best for exact-match lookups), while indexing walks a structure in two, three, or four steps (best for large files and range queries). Both cost something to maintain, and both save you from scanning every block. Next, the lecture zooms into the vocabulary of hashing itself: what a hash field is, what a hash key is, and what a hash function actually does.

The two techniques are not abstractions — they are the mechanisms behind everyday software. A login system that checks your email address uses an index to find your account among millions in one lookup. An in-memory cache (like the ones web servers keep for hot keys) uses hashing to answer "is this key cached?" in one step. And when you create a primary key in SQL, the database silently builds one of these structures for you. Understanding the trade-off — direct access for equality versus structured access for ranges — is what lets you explain why some queries are instant and others scan.

11.4 Hash Fields, Hash Keys, and Hash Functions

Hook: Two records can share a phone number, an address, or even a name — but a single wrong label can cost you a marks in an exam question: is the attribute you hash on a hash field or a hash key? The difference is one word in the lecture but a real property of the data.

11.4.1 The Hash Field and the Hash Key

Suppose a file has five attributes: name, id number, phone number, address, and email id. We want to hash on one of them — say the id number.

Hash field versus hash key. The hash field (the attribute on which we apply the hash function) is what the hash function reads. The function is generally denoted $H$ , and the value of the field that we feed into the function is called the key — so the key is a single value of the hash field, not the field itself. If the hash field happens to be a key of the relation — a unique identifier — it earns the stronger name hash key.

In the example file (name, id number, phone number, address, email id):

Hash on id number → every id is unique, so the hash field is also a hash key.
Hash on name instead → names can repeat, so we politely say it is a hash field, not a hash key.

By applying the function $H$ to the key value, we get an output that tells us in which block the data lives.

Vocabulary correction — why the distinction matters: a hash key is a hash field that is also a key of the relation (a unique identifier). If you call a non-unique attribute a hash key, you claim it identifies records uniquely when it does not — and that claim has consequences: a unique hash field guarantees one record per key, while a non-unique one gathers several records into the same bucket, which is exactly how collisions begin (Section 11.7).

11.4.2 What a Function Is

A hash function is a function like any other. In mathematics, a function is a subset of the cross product of a domain and a co-domain: you have an input set, an output set (also called the range), and among all possible combinations of inputs and outputs the function accepts only a limited subset.

Intuition — the professor's $x^{2}$ analogy: take $x^{2}$ — x squared: feed in 2 and you get 4, feed in 3 and you get 9, feed in 4 and you get 16. The input 2 never produces anything except the output 4 — only a limited set of combinations is allowed, even though the range could in principle contain everything. A hash function is exactly this kind of mapping: it maps an input to an output. The input is the key value (the hash field value); the output is the disk block address where the data can be found. The mapping is deterministic — the same key always produces the same address, so storing and retrieving follow the same rule.

Formalize — the hash function as a mapping. Write the hash function as

$H : K \to B$

where $K$ (the key space) is the set of all possible hash field values, $B$ (the bucket/address space) is the set of block addresses the file can live in, and $H$ sends each key $K \in K$ to exactly one block address $H (K) \in B$ . Every symbol: $H$ is the hash function (the rule), $K$ is one key value (one hash field value), and $H (K)$ is the block address for the record carrying that key.

Two properties make this mapping usable for storage:

Determinism — the same key always maps to the same address, so a record stored at $H (K)$ is found again at $H (K)$ .
Spreading — different keys should land on different addresses as often as possible, so no single block becomes a bottleneck.

That is the basic promise of the hash function — the "advertisement" for it, if you like: give it a key, and it tells you the block. How it actually achieves that is what the rest of the discussion builds up.

Scope and assumptions:

The hash function serves equality lookups only — "find the record whose key equals this value." It cannot answer "find records whose key is between 10 and 20"; that is indexing's job (Section 11.3).
The hash field should be stable — a record whose hash field changes must be deleted and re-inserted, because its address is computed from that value.
Uniqueness is not required for hashing to work — non-unique fields simply produce buckets holding several records (collisions), handled in Section 11.7.

11.4.3 Student Questions and Answers

Q: What is a hash field, and what makes it a hash key?

A: A hash field is the attribute on which we apply the hash function. In our example file — name, id number, phone number, address, email id — we chose the id number, so it is the hash field. If that field happens to be a key of the relation, we call it a hash key. The id number is a key, so here the hash field is also the hash key; if we hashed on name instead, which is not unique, we would only have a hash field.

Recap + bridge: The hash field is the attribute the hash function reads; the key $K$ is one value of that field; when the field is a unique identifier it is called the hash key; and the function $H$ maps every key to a block address — deterministically and evenly, we hope. The next section replaces the abstract $H$ with the first concrete hash function everyone meets: $h (K) = K mod M$ .

In practice this is the structure behind a phone-book-style lookup: your phone number (a near-unique key) is hashed to find your account record in a banking application, and web servers hash user session tokens to reach session data in one step. In file-organization terms, databases organize whole files around this idea — a hash file is a primary file organization whose block addresses come straight from the hash function applied to the hash field, which is the scheme the professor's courseware covers as static external hashing.

11.5 The K Mod M Hash Function

Hook: What is the fastest way to file a record so you never have to search for it? Take its number, divide by the size of your cabinet, and use the remainder as the drawer. That single trick — $K mod M$ — is the simplest and most famous hash function in the field, and everything else in this topic is a refinement of it.

11.5.1 What K and M Mean

One of the simplest hash functions is

$h (K) = K mod M$

Here $K$ is the key — the value of the hash field, for instance an id number — and $M$ is the number of storage locations we have set aside. The locations are numbered from 0 to $M - 1$ . Modulo (the remainder left over after dividing one number by another) gives back the remainder after dividing $K$ by $M$ , so the output always falls in $0 \dots M - 1$ — exactly the range of location numbers. If we have 10 locations, every key lands on one of the indices 0 through 9. Because the output range of $h$ is exactly the set of locations, every key is guaranteed to have somewhere to go — no key can compute an address that does not exist.

Formalize — why the remainder is the address. Dividing $K$ by $M$ leaves one of exactly $M$ possible remainders: $0, 1, 2, \dots, M - 1$ . So $K mod M$ maps any key, however large, into the address space of the file. Example values with $M = 10$ :

$24 mod 10 = 4$
$17 mod 10 = 7$
$90 mod 10 = 0$
$103 mod 10 = 3$

Each key lands in the location numbered by its remainder; keys that differ by a multiple of $M$ (like 24 and 34) land on the same location — that repetition is the seed of collisions (Section 11.7).

11.5.2 Worked Example: 24 mod 10

Worked example — storing and retrieving 24 with $M = 10$ locations.

Step 1 — compute the address: $K = 24$ , $M = 10$ . Divide: $24 \div 10 = 2$ with remainder $4$ . So $24 mod 10 = 4$ .

Step 2 — store: the record for key 24 is placed at location 4 — the fifth location, counting 0, 1, 2, 3, 4. (Note the counting: location 4 is not the fourth slot; slot numbering starts at 0.)

Step 3 — retrieve: someone asks for the record with id 24. The system does not search anything. It computes $24 mod 10 = 4$ and goes straight to array index 4, where the data sits.

Step 4 — compare: one check confirms the record found is the right one; if two keys ever share a location (Section 11.7), this is where the collision handling begins.

Sense-check: storing and retrieving follow the same rule, so the lookup is direct — one computation, one location, no scanning. That is the whole basic idea of this hash function: the structure tells you where the record lives without scanning.

Pitfalls:

Off-by-one counting. $24 mod 10 = 4$ means the fifth slot (index 4), not the fourth. Locations are numbered from 0 to $M - 1$ .
Confusing mod with integer division. $24 mod 10 = 4$ is the remainder; $24 \div 10 = 2$ is the quotient. The hash uses the remainder.
Expecting distinct keys to always get distinct addresses. They cannot: infinitely many keys, only $M$ locations — collisions are inevitable and are handled, not avoided.
Choosing $M$ carelessly. For the mod function, prime $M$ spreads real-world keys better; $M$ that shares factors with the key values cluster records into few locations.

11.5.3 Buckets Instead of Exact Addresses

The input range is usually larger than the number of locations. We may have input values from 0 to 100 while only 10 entries actually exist, so we create 10 buckets and place each entry by its hash value mod 10.

Intuition — buckets, not precise slots. A bucket is a container that holds several records (in disk terms, one disk block or a cluster of contiguous blocks). In internal hashing (hashing inside main memory, Section 11.6) the entry can be stored exactly as the function says — location 4 really holds key 24. In external hashing (hashing to reach data on disk), $24 mod 10 = 4$ is not the exact address on disk; location 4 holds a structure — the bucket number or a pointer — which in turn tells you the exact place where the data is stored. So when the actual storage is not exactly what the hash function computes, the structure at the computed location bridges the gap between the bucket and the real block address. The hash function finds the right bucket; the bucket finds the right block.

Recap + bridge: $h (K) = K mod M$ names its symbols — $K$ the key value, $M$ the number of locations numbered $0 \dots M - 1$ — and returns the remainder as the address, so storing and retrieving are one computation each. The same rule runs in two settings: inside memory, where the address is exact (internal hashing), and on disk, where the address leads to a bucket that holds the real block address (external hashing). That two-setting split is the next section's topic.

The $K mod M$ function is the workhorse of everyday computing: programming-language hash tables, dictionaries, and caches size their array to a prime $M$ and map every key through exactly this remainder step. Databases use the same idea when a file is organized as a static hash file — a fixed number of buckets, each a disk block, reached by $h (K) = K mod M$ — which is how the reference textbooks describe hashing for disk files. When you later judge hash-based indexing for the HealthTrack schema, this is the foundation you are reasoning from.

11.6 Internal Hashing and External Hashing

Hook: The same hash function runs in two very different worlds: inside the computer's main memory, where location 4 really is location 4, and on disk, where the computed "address" is only a bucket number that still has to be translated into a real block. Confusing the two worlds is one of the most common conceptual slips in this topic.

11.6.1 Internal Hashing

Internal hashing is hashing done inside the main memory. Why would we hash inside main memory at all, when we already hashed to get the block in? Because even after a block is pulled into memory, we still want fast access within the block. The same idea that made disk access fast can make in-memory access fast too, and $K mod M$ is one of the algorithms used for it.

How internal hashing works. Internal hashing is implemented as a hash table: an array of $M$ slots in memory, numbered $0$ to $M - 1$ , with the hash function choosing the slot. The defining property is that the data is stored exactly as computed — location 4 really holds key 24. No bucket table, no pointer, no second step: the computed value is the address. This is the form of hashing familiar from programming-language dictionaries and symbol tables, where the whole structure lives in RAM and the access is one array read.

11.6.2 External Hashing

External hashing is hashing to reach data on the disk, where the computed value is a bucket number rather than the exact address. Here the file is large — thousands, hundreds, or millions of records — and the records are chunked together into blocks.

How external hashing works — the bucket technique. The hash function maps a key to a bucket number; a bucket is one disk block or a cluster of contiguous disk blocks. A table kept in the file's header converts each bucket number into the corresponding disk block address. So the lookup runs in two hops:

Compute $h (K)$ → bucket number.
Read the header table → the block address of that bucket → pull the block into memory.

Because the real address is unknown until we look at the bucket, external hashing requires this separate structure that stores the exact place for each entry. The reason for the indirection: on disk the relative bucket number means nothing to the disk arm — it needs an absolute block address, and the header table is what converts one into the other.

Visual intuition: picture a small lookup table as the file's cover page — bucket number on the left (0, 1, 2, …, $M - 1$ ), block address on the right. The hash function hands you a bucket number; you slide a finger across the cover page to the block address; then the disk fetches that block. Landmarks: the two-hop path (hash → bucket → block) is the entire difference from internal hashing's one-hop path. One-sentence takeaway: internal hashing computes where the record is; external hashing computes which bucket it is in, and the header table finishes the job.

External hashing itself splits into two regimes:

	Static external hashing	Dynamic hashing
Buckets	Fixed set set up in advance	The set grows with the data
When the file overflows	Long overflow chains slow retrieval; whole-file reorganization	Localized splits; only the overflowing bucket reorganizes
Cost	No directory overhead	A directory or similar structure

Static external hashing allocates a fixed number of buckets $M$ once, so at most $m \times M$ records fit (where $m$ is the capacity of one bucket) — fewer records waste space, more records pile into overflow chains. Dynamic hashing grows the bucket count with the data and reorganizes only locally. Extendible hashing, discussed next, is the dynamic scheme — the first technique in this course that extends its addressing range on demand.

11.6.3 Student Questions and Answers

Q: When we create primary key or foreign key constraints in a database, it usually uses an index as a junction structure. Can we instead use hashing as the default when creating such a constraint — like writing "hash by this" where we would normally create an index?

A: I have not tested that, so I cannot answer it right now — it needs checking. Note that indexes themselves are not covered yet; we are doing hashing first and indexing after, so your question is relevant but best held until indexing is on the table. Keep the question — when indexing is covered, compare the two structures directly.

Q: Is hashing only a function — some kind of mapping function — or is there a difference between hashing and data-structure approaches like B+ trees and hash tables?

A: For hashing I can tell you now: it is not just one hash function and done. It is a proper system — we have the way to access it, and we have ways to handle collisions. We have only scratched the surface so far. Next we will discuss dynamic hashing, which will show how the whole system fits together. You will get the indexing side of the answer once we reach indexing.

Recap + bridge: Internal hashing stores records exactly where the function computes — one hop, no structure. External hashing maps keys to bucket numbers and uses a header table to reach the real block — two hops — and divides into static hashing (fixed buckets) and dynamic hashing (buckets grow with the data), with extendible hashing as the dynamic scheme coming next. Before the structure can grow, though, hashing must handle its daily reality: two keys landing in the same bucket — collisions.

Both flavors power real systems. In-memory caches and database buffer managers use internal hashing for one-step key lookup in RAM. On disk, relational systems organize files with static external hashing when the file size is predictable, and move to dynamic schemes when records accumulate unpredictably — for example, log-heavy tables in analytics workloads, where the bucket count must grow without rebuilding the whole file. Understanding which world a hash runs in tells you whether the computed value is an address (memory) or a promise to look up (disk).

11.7 Collisions and Collision Handling

Hook: Three different records, one identical address: 11, 51, and 91 all compute to bucket 1. This is not an accident, a bug, or bad luck — it is mathematically unavoidable, and every serious hashing design begins by planning for it.

11.7.1 When Collisions Happen

Because the input range is larger than the number of buckets, and because the data is random, different keys can map to the same location.

The collision, defined. Suppose we are storing 11, 51, and 91 with $h (K) = K mod 10$ :

$11 mod 10 = 1$
$51 mod 10 = 1$
$91 mod 10 = 1$

All three satisfy $x mod 10 = 1$ , so all three fall into bucket 1. That situation is a collision — two or more distinct keys claiming the same bucket. Collisions are expected, not exceptional: the whole design of a hashing scheme includes what happens when the computed location is already occupied.

Why are collisions unavoidable? The key space is huge — millions of possible keys — while the address space has only $M$ buckets. By the pigeonhole principle (if there are more objects than boxes, some box receives at least two objects), once more than $M$ distinct keys are stored, some bucket must receive at least two. Even below $M$ keys, random keys spread unevenly: with $M = 10$ and only 10 random keys, the chance that no two collide is under 4%. So the question is never "will we collide?" but "how do we recover when we do?"

11.7.2 The Main Handling Techniques

There are various ways to handle collisions. Each technique changes how insertion, retrieval, and deletion behave, so choosing one is a real design decision, not a detail.

Open addressing. A collision is resolved by probing nearby locations until a free slot is found. Starting at the occupied location, the scheme checks the next slot, then the next, wrapping around the end of the array, until an empty one appears. Algorithmically: try $(h (K) + 1) mod M$ , then $(h (K) + 2) mod M$ , and so on.

Trace — open addressing with $M = 10$ : insert 11, then 51, then 91.

Insert 11 → $11 mod 10 = 1$ → slot 1 is free → 11 sits in slot 1.
Insert 51 → $51 mod 10 = 1$ → slot 1 is occupied → probe slot 2 → free → 51 sits in slot 2.
Insert 91 → $91 mod 10 = 1$ → slot 1 occupied → slot 2 occupied → probe slot 3 → free → 91 sits in slot 3.

Retrieving 91 walks the same probe sequence: slot 1 (not 91), slot 2 (not 91), slot 3 (91 found). The cost is the length of the probe run — which is why keeping the table below full matters.

Sense-check: three inserts, one location per key plus probing, and every key is still reachable by the same deterministic walk.

Chaining. Each bucket holds a chain of records; colliding keys are simply appended to the chain. Typically the array is extended with overflow locations, each bucket keeps a pointer to its chain, and a collision is resolved by placing the new record in an overflow location and linking it to the chain.

Trace — chaining with $M = 10$ : insert 11, then 51, then 91.

Insert 11 → bucket 1 → chain: [11].
Insert 51 → bucket 1 → append → chain: [11 → 51].
Insert 91 → bucket 1 → append → chain: [11 → 51 → 91].

Retrieving 91 needs one bucket access plus walking the chain. Deletion is simple — unlink the record from the chain. In external hashing, this is overflow chaining: each full bucket points to a linked list of overflow blocks.

Sense-check: one computation still finds the right bucket; the chain absorbs everything extra, at the cost of scanning the chain when it grows long.

Multiple hashing. If the first hash function collides, a second function is applied to find an alternative location; if that also collides, a third function or open addressing takes over. Each failed function hands the record to the next rule in line.

Trace — multiple hashing: with $h_{1} (K) = K mod 10$ and $h_{2} (K) = (K mod 7) + 2$ :

Insert 11 → $h_{1} (11) = 1$ → free → slot 1.
Insert 51 → $h_{1} (51) = 1$ → occupied → try $h_{2} (51) = (51 mod 7) + 2 = 2 + 2 = 4$ → free → slot 4.
Insert 91 → $h_{1} (91) = 1$ → occupied → try $h_{2} (91) = (91 mod 7) + 2 = 0 + 2 = 2$ → free → slot 2.

Sense-check: a second function spreads the colliding keys over new addresses instead of piling them into one probe run or chain.

Pitfalls:

Designing a hash scheme without a collision plan. Collisions are certain; a scheme without overflow handling fails the moment two keys agree.
Letting chains or probe runs grow unchecked. Retrieval degrades from "one or two steps" to "scan the whole chain." The reference treatment recommends keeping hash tables between 70 and 90 percent full so collisions stay rare.
Deleting carelessly under open addressing. Removing a record blindly can break the probe sequence for later records; deletion under open addressing needs tombstones or rehashing, which is why chaining is preferred on disk.
Believing a perfect hash function eliminates collisions. No function from a large key space to a small bucket space can; at best a good function spreads keys evenly.

Recap + bridge: A collision is two or more distinct keys claiming the same bucket — inevitable by counting. The three classic answers are open addressing (probe onward), chaining (append to the bucket's chain), and multiple hashing (retry with another function), each with its own insertion, retrieval, and deletion behavior. Collision handling is a first-class part of any hashing design. The next section takes the same problem — buckets that fill up — and solves it at the design level: instead of overflow chains, extendible hashing splits the bucket itself.

Collision handling is everywhere in production systems: in-memory caches use open addressing for cache lines, programming-language hash tables default to chaining, and databases organize static hash files with overflow chaining when a bucket fills. When a web service suddenly slows down as its in-memory cache fills, the usual culprit is exactly this — a collision structure grown long. The same thinking applies to the HealthTrack schema: if you choose hash-based indexing, you are implicitly choosing how your collisions will be handled.

11.8 Extendible Hashing: Global Depth and Local Depth

Hook: Static hashing picks the number of buckets once and lives with the choice — too many buckets waste space, too few drown in overflow chains. Extendible hashing refuses the choice: it grows exactly the parts of the structure the data demands, one bucket at a time, and only doubles its directory when a bucket genuinely runs out of address bits.

11.8.1 The Idea: Address by the Last d Bits

Extendible hashing is the dynamic scheme: instead of fixing the number of buckets once, the structure grows as records are inserted. The core idea is to address buckets by the last few bits of the binary form of the hash value. If the hash of a key, written in binary, ends in the two bits 10, the key is sent to the bucket labeled 10.

Formalize — how many buckets $d$ bits give you. With $d$ bits there are exactly $2^{d}$ distinct patterns, so with $d$ bits you address $2^{d}$ buckets:

$N_{buckets} = 2^{d}$

Every symbol: $d$ is the number of bits read from the hash value (the directory's depth), and $2^{d}$ is the number of bucket labels the directory can hold. With three bits you address eight buckets (000 through 111); with $d$ bits, $2^{d}$ buckets. For example, $32 mod 10 = 2$ , and 2 in binary is 0010; the last two bits are 10, so 32 goes to the bucket labeled 10. The same rule drives every lookup: compute the hash value, take its binary form, read the last $d$ bits, and go to the labeled bucket.

11.8.2 Global Depth and Local Depth

The directory of the structure is governed by the global depth, $d_{g}$ : the directory uses the last $d_{g}$ bits and so has $2^{d_{g}}$ entries. Each bucket carries its own local depth, $d_{l}$ : the number of bits actually used to distinguish the entries inside that bucket.

The two depths, side by side.

	Global depth $d_{g}$	Local depth $d_{l}$
Attached to	The directory as a whole	Each bucket individually
What it means	How many bits the directory reads → $2^{d_{g}}$ entries	How many bits the bucket's records share
Grows when	The directory doubles (an overflowing bucket had $d_{l} = d_{g}$ )	That bucket is divided into two (always)

A bucket with local depth 1 distinguishes entries only by the last bit — last digit 0 goes to one bucket, last digit 1 to another — even though the directory as a whole may use two bits. The two depth numbers exist precisely so that parts of the structure can grow independently: one busy bucket can grow without touching the others, and only when it is already at the global depth does the directory itself have to double.

Visual intuition — the starting structure. The example begins with global depth 2: the directory is a row of four slots labeled 00, 01, 10, 11. But buckets are fewer than slots — the four entries point to two buckets: slots 00 and 10 both point to the bucket for keys ending in bit 0 (local depth 1), and slots 01 and 11 both point to the bucket for keys ending in bit 1 (local depth 1). Two directory entries sharing one bucket is normal; it means that bucket has not yet needed to distinguish those bits. One-sentence takeaway: the directory is the street map — several streets can lead to the same neighborhood, and a neighborhood only divides when it fills up.

11.8.3 Worked Example: Inserting 32, 28, 43, 15, 48, 66

Let us walk the courseware example the way it was presented in class, using the hash rule "compute the value, take the binary form, and use the last bits as the bucket label." The structure starts at global depth 2 with two buckets of capacity 2 — bucket 0 for keys ending in bit 0, bucket 1 for keys ending in bit 1 — and the directory entries 00, 01, 10, 11 pointing to them.

Worked example — inserting 32, 28, 43, 15, 48, 66, one record at a time.

#	Key	Hash value $K mod 10$	Binary	Last 2 bits	Bucket action
1	32	2	0010	10	Bucket 0 → {32}
2	28	8	1000	00	Bucket 0 → {32, 28}
3	43	3	11	11	Bucket 1 → {43}
4	15	5	101	01	Bucket 1 → {43, 15}
5	48	8	1000	00	Bucket 0 is full — overflow
6	66	6	110	10	Bucket for 10 → {32, 66}

Step 5 in detail — the split. 48 computes to bucket 0, but bucket 0 already holds {32, 28} and has capacity 2. Check the depths: the overflowing bucket's local depth is 1, the global depth is 2 — local depth is less than global depth, so only this bucket splits:

Increase bucket 0's local depth from 1 to 2.
Allocate a new split image.
Rehash the bucket's contents (32, 28, and the new 48) by the last two bits: 32 → 10, 28 → 00, 48 → 00. So the bucket labeled 00 gets {28, 48}, and the bucket labeled 10 gets {32}.

In the directory, the entry 00 and the entry 10 now point to two different buckets instead of both pointing to the same one.

Step 6. 66 computes to 10 → bucket {32} has room → {32, 66}.

Final state: global depth 2; directory 00 → {28, 48}, 01 → {43, 15}, 10 → {32, 66}, 11 → {43, 15}; local depths 2, 1, 2.

Sense-check: four records end in bit 0 and three in bit 1, but after the split no bucket holds more than its capacity of 2, and the directory did not need to double because the split bucket had spare address bits. The class-time variant — inserting only 32, 48, 15, 66 — reaches the same final structure with the split triggered by 66 instead of 48: the split rule is order-independent because it is always "overflow → raise local depth and rehash by one more bit."

The split rule, in words: a bucket overflows → first raise its local depth and rehash its contents by one more bit. If the local depth was already equal to the global depth, raise the global depth as well, which doubles the directory so the new buckets can be addressed. Only records of the overflowing bucket move; every other bucket is untouched.

11.8.4 When Local Depth Equals Global Depth

The interesting case is when the overflowing bucket already has local depth equal to the global depth. Then there are no spare bits to separate the colliding keys — every bit pattern that could be used is already spoken for in the directory. The remedy is to increase the global depth: the directory doubles in size, every entry gains one more bit, and the split proceeds.

Worked example — the directory doubles. Continue from the final state above: directory 00 → {28, 48}, 10 → {32, 66} (both local depth 2), 01 and 11 → {43, 15} (local depth 1); global depth 2. Insert 96: $96 mod 10 = 6$ , binary 110, last two bits 10 → bucket {32, 66} — full.

Depth check: this bucket's local depth is 2, equal to the global depth 2 — no spare bits remain.
Double the directory: global depth becomes 3, and the directory grows from 4 to 8 entries (000, 001, …, 111). Every old entry is copied so the pairs that differ only in the third bit (000/100, 001/101, …) start by pointing to the same bucket.
Split and rehash by three bits: the overflowing bucket's records (32, 66, 96) are redistributed by the last three bits: 32 → 010, 66 → 110, 96 → 110. So bucket 010 gets {32}, and the new split image 110 gets {66, 96}.

Final state: global depth 3; the 8-entry directory routes 000/100 → {28, 48}, 001/011/101/111 → {43, 15}, 010 → {32}, 110 → {66, 96}; local depths 2, 1, 3, 3.

Sense-check: two directory entries (010 and 110) were "created" by the doubling — the extra bit is exactly what separated the colliding keys. Nothing else in the file moved.

This is the "extendible" part of the name: the structure extends its addressing range only when the data actually demands it, rather than paying for a huge fixed directory from the start. Values keep being inserted, buckets keep splitting, and from time to time the directory doubles — exactly the growth pattern of dynamic hashing.

Pitfalls:

Doubling the directory on every split. Wrong — most splits are handled at local depth below the global depth, with no directory change. Only a split of a bucket at $d_{l} = d_{g}$ doubles it.
Rehashing more than the overflowing bucket. Only that bucket's records move; rehashing the whole file destroys the point of extendible hashing.
Forgetting that directory entries share buckets. Two entries (e.g., 01 and 11) pointing to one bucket is legal — it means that bucket's local depth is below the global depth.
Mixing up bit conventions. The lecture addresses by the last bits, so the directory can double by simple copying; the reference texts describe both conventions, and the last-bit convention is the standard one in practice.

11.8.5 Exam Note and Practice Guidance

Exam note: this particular topic — extendible hashing with global and local depth — may come up in the comprehensive examination. Do not assume that watching the walkthrough once is enough. Take the very same numbers (32, 28, 43, 15, 48, 66) and apply extendible hashing yourself — step by step, on paper, drawing the directory and the buckets after every insert. Practicing on the same numbers will honestly reveal what you thought you understood and what you still did not understand.

Understanding more than 20% of the walkthrough on the first pass is a perfectly fine start — the rest arrives through practice. The courseware session on extendible hashing presents the exact same case study with the exact same numbers, so working through it once more with the structure in front of you is the recommended path before the next session.

Recap + bridge: Extendible hashing addresses buckets by the last $d$ bits of the hash value: the directory has $2^{d_{g}}$ entries (global depth) and each bucket records how many bits its records actually share (local depth). Overflow raises the local depth and splits only that bucket; when local depth already equals global depth, the directory doubles. The structure grows in small, local steps — the defining behavior of dynamic hashing. Next sessions carry the same "find the block" question into indexing, where B+ trees answer it for ranges and sorted access.

In the real world, extendible hashing is the classic choice for files that must support exact-match lookup while the data volume is unpredictable — the textbook case being large keyed files (like customer or subscriber tables) whose sizes grow in spurts. Because a lookup costs one directory read plus one block read, and because growth never reorganizes the whole file, it behaves like static hashing's speed without static hashing's fixed-size commitment. When the HealthTrack assignment asks you to justify hash-based indexing for your schema, this is the mechanism you are describing: direct equality access that can grow with your data.

11.9 Assignment: HealthTrack

Hook: This assignment hands you no entities, no attributes, no tables — only a client's description of a health application. That is the point: in real life, the database designer's first job is deciding what the data model should be. HealthTrack asks you to run the entire design pipeline you have been learning — from the specification to the schema to working SQL — for 15 marks.

11.9.1 The Problem Description

The assignment is to build the database design for a web-based software application called HealthTrack. Its users are individual patients, healthcare providers such as doctors, and researchers:

Patients get a centralized platform to store and access their medical history, prescriptions, and related data.
Healthcare providers can access patient records and the information they need for decision-making.
Researchers can use anonymized data for studying and making health trends.

The functions the application supports: patients store their medical history; patients schedule appointments; the application offers medication reminders and a medical log; users use the log to track health metrics over a period of time — for example, recording blood pressure and observing how it has changed; patients can share their data records with family members and others when needed; and the application can find insights from the personal information it holds.

Treat this as a genuine client scenario. A client walks in with a user specification, and you — acting as a database administrator or database designer leading the database team — have to interpret it. In real life the client does not hand you the entities and attributes; you ask corner-case questions ("does the application involve this or that?") and you make the design decisions yourself. Every assumption you state is a design decision you are taking ownership of.

11.9.2 Submission and Deliverables

The submission is a single Word or PDF document: a written or typed report. It carries 15 marks, is submitted individually, and the deadline is the 19th of April 2024 — extended to the 30th of April 2024 after the class discussion. The report must include, in order:

Problem description — a brief description; you may carry the exact description given in the handout, so that the ER diagram is built from the same starting point.
ER diagram — entities such as users, health records, appointment, medication, and health metrics, with the relationships between them. You may add or remove entities as you see fit.
Relational model — the conversion of the ER diagram, using the method discussed many times in the course.
Normalization — convert the relational model into 3NF.
SQL queries — insertion, deletion, updation; data definition language (DDL) queries for creating the schema; and some more complex queries that support analytics on the data. Write at least five queries, and make sure they have some complexity — a plain SELECT * does not count. The level of complexity is left to you.
Snapshots — the queries must be executed on your own system, and you must take a snapshot of the executing query and its result to include in the report.
Indexes — from this and the next session's material, describe what type of indexing you would use — hash-based indexing or normal indexing, and how. This is theoretical; you are not required to write indexes in SQL. The point is to show you know what indexes are and which kind fits your schema.

Exam note (assignment): 15 marks, individual submission, single Word or PDF report, due 30 April 2024, uploaded through the e-learn portal (you may know it as Takshila). Everyone has the same assignment topic, and you may discuss with each other — but the attempt itself must be individual.

11.9.3 Academic Integrity and the Self-Declaration

The assignment is a skill-building exercise, so the integrity policy is strict: use your own work, do not use AI tools to write anything, you may discuss with each other but must not copy, and plagiarism in any form is highly discouraged.

The self-declaration. Along with the report you must submit a self-declaration with your name and your id number, stating that:

all components submitted are your original work,
you have not used any AI tool,
the work is your individual work,
you have not shared or copied your work to others,
you understand that violating this policy is not conducive to healthy learning and the development of meaningful skills — and that genuinely attempting the assignment results in long-term learning and personal growth.

Sign it; it is part of the submission.

11.9.4 Student Questions and Answers

Q: Should we write down the assumptions we take while designing?

A: Yes — write every assumption out before drawing the ER diagram. For example, if you assume one student can have an interaction with more than one health record, or that a patient can have more than one assignment to a provider, state it. In any question, whatever the course, if you want to take an assumption, write it and go ahead — it will be helpful for grading and shows the design is deliberate.

Q: The ER diagram generated by tools like SQL Workbench or MySQL — is that acceptable?

A: Those tools generally do not use the same notation and cardinality conventions we discussed in the course — their representation does little justice to the technical details we covered. I would be happy if you draw the ER diagram with pen and paper instead, using the textbook representation. Tool-generated diagrams are still worth reading in practice, but for this submission the textbook-style diagram is preferred.

Q: Is there a reference database to be used, or do we create the database ourselves?

A: Create and populate it yourself. Everyone will have a different relational schema and a different number of tables, because your ER diagrams will differ. You are free to use any dummy data to populate your database and to write your queries against it.

Q: Approximately how many queries do you expect — four, or eight?

A: At least five. I am not saying you cannot write eight, and writing only four will not give you zero marks — but five queries with some depth will show me you have done it nicely. A query is not expected to be astronomically perfect; some complexity is what I am looking for. Simple single-table selects are not enough; joins, aggregations, and analytics-style queries show the schema actually works.

Q: Ten days is too short to submit the assignment; we need more time.

A: Agreed — the deadline moves to the 30th. And a piece of advice that applies here: do not chase perfection. Whatever comes to your mind first, get it done; done is always better than perfection, and you can improve it afterwards. The tendency to think in "either success or failure" is not conducive to progress.

Q: Could you have given us the relational schema itself — the tables — instead of just the description?

A: No, and that is deliberate. In real life the client does not give you the attributes and entities; you get a description and you derive the schema. The statements in the handout already give you a good sense of the entities — you then assume the attributes. That is the skill this assignment builds.

Recap — the working recipe for HealthTrack: (1) read the description as a client specification; (2) write every assumption before the ER diagram; (3) draw the ER diagram in textbook notation — pen and paper; (4) convert it to a relational model; (5) normalize to 3NF, checking lossless join and dependency preservation from Section 11.1; (6) write at least five SQL queries with real complexity plus DDL, run them, and snapshot the results; (7) justify your indexing choice — hash-based or normal — using Sections 11.3 to 11.8; and (8) attach the signed self-declaration and upload before the 30th.

The HealthTrack scenario is deliberately realistic — patient portals, medication reminders, and anonymized health analytics are exactly the kind of system healthcare technology companies build today. The pipeline you practice here (specification to normalized schema to working SQL) is the same one used whenever a product team hands a database team a feature description: the designer decides the entities, the designer justifies the constraints, and the designer proves the design with queries. Done deliberately, the report itself is a portfolio piece.

11.10 Road Ahead: Indexing, Transactions, and Revision

11.10.1 The Remaining Sessions

Five sessions remain in the course. The next session is expected to complete the indexing portion, including B+ trees and indexing in detail. After that come transaction concurrency and the other topics that are still pending. One session near the end is reserved for revision, which will help many of us consolidate and do a lot more.

Scope: a note on scope — query optimization is not part of this course. The material you must own is the arc this lecture opened: finding the block (hashing and indexing), and the correctness topics still to come (transactions and concurrency).

Recap + bridge: hashing and indexing answer the same question — which block holds the record — each in its own style, and the next session finishes the indexing side with B+ trees. The session after that moves from where the data is to who may touch it when: transactions and concurrency, the topics that keep simultaneous users' data consistent. That is the second half of the course's fundamentals.

11.10.2 The Commitment Trick and Courseware Sessions

Before the next session, you are expected to review the courseware sessions 5.3 and 5.4, which cover B+ trees and indexing. At normal speed this is no more than a couple of hours of reading — faster at higher speed, so take it easy. The more you read, the more the next session becomes a revision for you.

Exam note (preparation): review courseware sessions 5.3 and 5.4 on B+ trees and indexing before the next session — about two hours at normal speed. The next session then completes indexing, and one session before the end is reserved for revision, which covers the consolidated material.

The class was asked to type "yes" to commit to listening, and the point is real: those who said yes have a roughly 90% higher chance of actually following through; those who did not say yes have a roughly 90% lower chance. Publicly stating the commitment changes the odds of doing it — a small self-management trick you can carry into any course. Whether you typed it or not, the reading list stands: two hours of courseware now turns next session into revision instead of new material.

Exam Guidance Summary

Quiz 2 decomposition question: the statement "decomposition into 3NF or BCNF may not always be dependency preserving, but guarantees lossless join" mixes two normal forms with different guarantees. 3NF is always dependency preserving and lossless join (when decomposed properly); BCNF may not always be dependency preserving, and a BCNF decomposition is lossless only if you decompose the proper way — some BCNF decompositions are not lossless. Both option C and option D were accepted as the most appropriate answers, and the marks will be updated.
Lossless join and dependency preservation: lossless join is required at every step from 1NF through BCNF — a decomposition is lossless when the join of its relations reproduces exactly the original data with no spurious tuples. Dependency preservation is required from 1NF through 3NF; at BCNF it is acceptable to miss some dependencies because BCNF buys very low redundancy at that cost. The guarantees hold when you follow the algorithm — for a violated $X \to Y$ , make a separate relation $X Y$ , remove $Y$ , and keep $X$ in the original — and weaken under ad hoc decomposition.
Extendible hashing: expect a question on global depth and local depth in the comprehensive examination. Practice by applying extendible hashing to the same numbers (32, 28, 43, 15, 48, 66) on paper, drawing the directory and buckets after every insert; understanding more than 20% of the walkthrough on the first pass is a fine start, and the rest comes from practice. The courseware session on extendible hashing presents the exact same case study. Recall the split rule: overflow raises the bucket's local depth and splits only that bucket; when local depth equals global depth, the directory doubles.
Assignment: HealthTrack is worth 15 marks, individual submission, single Word or PDF report due 30 April 2024 (originally 19 April, extended in class). Required: problem description, ER diagram (textbook notation, pen and paper preferred), relational model, 3NF conversion, at least five SQL queries with real complexity (not SELECT *) plus DDL, snapshots of the queries executed on your own system, and a theoretical indexing discussion (hash-based vs normal indexing — no SQL indexes required). Include the signed self-declaration with your name and id number. Upload through the e-learn (Takshila) portal.
Assumptions: in the assignment and in any exam question, write every assumption out before proceeding.
Before the next session: review courseware sessions 5.3 and 5.4 (B+ trees and indexing) — about two hours at normal speed. The next session completes indexing; then transactions and concurrency; one session is reserved for revision. Query optimization is not in this course.
Quiz marks: the normalization-related quiz 2 marks are being updated and will appear soon.

Key Industry Applications

Real-world: hashing is the standard file-organization technique for finding which disk block holds a record, which is exactly how database systems decide where to read, insert, update, and delete.
Real-world: the same hashing constraints and requirements reappear in other courses and in real life — the technique transfers wherever fast lookup by a key is needed.
Real-world: the index at the back of a book (keyword topic → page number) is the everyday analogue of a database index; B+ tree indexing is the scalable choice for large files and range queries.
Real-world: organizing a computer's D drive into course folders is the user-level version of what indexes do on disk — an ordering that makes retrieval fast.
Real-world: in SQL systems, creating a primary key or foreign key constraint typically creates an index behind the scenes; whether hashing can substitute for that default index is an open practical question worth testing on a real database.
Real-world: in-memory caches and programming-language hash tables use internal hashing ( $K mod M$ ) for one-step key lookup in RAM, and databases organize static hash files with overflow chaining for predictable-size tables.
Real-world: extendible hashing serves keyed files whose size is unpredictable — customer or subscriber tables that grow in spurts — because lookups stay at one directory read plus one block read while growth never reorganizes the whole file.
Real-world: HealthTrack — a web application with patients, doctors, and researchers, storing medical history and prescriptions, scheduling appointments, sending medication reminders, tracking health metrics like blood pressure over time, sharing records with family, and analyzing anonymized data for health trends — is a realistic software-product scenario for the full design pipeline: user specification → ER diagram → relational model → 3NF → SQL.

DDA Lecture 11 notes · Hashing, Extendible Hashing, and the HealthTrack Assignment

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

Sections Breakdown

111.1 Quiz 2 Review: Decomposition, Dependency Preservation, and Lossless Join

Review of quiz 2: the decomposition statement that mixes the guarantees of 3NF and BCNF; lossless join (no spurious tuples) required from 1NF through BCNF, dependency preservation required through 3NF and relaxable at BCNF; following the algorithm versus ad hoc decomposition.

211.2 Storage Fundamentals: Why Database Access Is Disk-Bound

Why database access is disk-bound: hard disk versus main memory, platters, tracks, sectors, and blocks, the 50,000-transfer join example, and organizing the disk like a filing system.

311.3 Hashing and Indexing: Two Techniques for Finding the Block

Hashing and indexing as the two techniques for finding the block that holds a record: direct access in one or two steps versus walking a structure in two to four steps, with the book-index model and the comparison table.

411.4 Hash Fields, Hash Keys, and Hash Functions

Hash fields, hash keys, and hash functions: what a mathematical function is, H mapping the key space to the bucket space, equality-only scope, and why a hash key must be a key of the relation.

511.5 The K Mod M Hash Function

The K mod M hash function: what K and M mean, why the remainder is the address, the 24 mod 10 worked example, buckets instead of exact addresses, and the classic mod-related pitfalls.

611.6 Internal Hashing and External Hashing

Internal hashing, which stores data exactly at the computed location, versus external hashing, which computes a bucket number and reads a header table for the real block address; static external hashing versus dynamic hashing.

711.7 Collisions and Collision Handling

Collisions and collision handling: why collisions are inevitable by counting, and the three classic techniques — open addressing, chaining, and multiple hashing — with traces for each.

811.8 Extendible Hashing: Global Depth and Local Depth

Extendible hashing: addressing buckets by the last d bits of the hash value, global depth and local depth, the 32, 28, 43, 15, 48, 66 worked example, and when the directory doubles.

911.9 Assignment: HealthTrack

The HealthTrack assignment: the problem description, the 15-mark individual report deliverables (ER diagram, relational model, 3NF, five complex SQL queries with snapshots, theoretical indexing choice), and the signed self-declaration.

1011.10 Road Ahead: Indexing, Transactions, and Revision

Road ahead: the next session completes indexing with B+ trees, then transactions and concurrency, then a revision session; review courseware sessions 5.3 and 5.4 before the next class.

11Key Industry Applications

Hashing and extendible hashing in production: static hash files, in-memory caches, B+ tree indexing, primary-key indexes behind SQL constraints, and the HealthTrack pipeline as a realistic healthcare scenario.

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.

Quiz 2 Review: Decomposition, Dependency Preservation, and Lossless Join

Must-know: Lossless join (no spurious tuples) is required from 1NF through BCNF; dependency preservation is required through 3NF but may be compromised at BCNF. The guarantee depends on decomposing by the algorithm: for a violated X -> Y, create XY, remove Y, keep X.

$X \to Y$

⚠️ Top pitfall: Assuming BCNF always guarantees lossless join: a decomposition reached by an ad hoc path can be in BCNF and still fail the lossless-join test because the shared attribute is a key of neither side.

Self-check: Is the join of two relations on a common attribute that is a key of neither relation lossless?

Storage Fundamentals: Why Database Access Is Disk-Bound

Must-know: The processor never sees disk data directly; every operation pulls blocks from disk into main memory, and query cost is counted in block transfers.

⚠️ Top pitfall: Thinking the processor can work on data still on disk, or measuring query cost in instructions instead of block transfers.

Self-check: Why does a query that fetches a few rows still cost many disk accesses?

Hashing and Indexing: Two Techniques for Finding the Block

Must-know: Hashing gives direct access in one or two steps and suits exact-match retrieval; indexing (especially B+ trees) scales to large files and shines for range queries but takes two to four tries and costs storage, processing, and energy to maintain.

⚠️ Top pitfall: Assuming hashing is ideal for every lookup - it is poor for range queries, where an index on sorted keys wins.

Self-check: Which technique would you choose for a query asking for all students with marks in an interval, and why?

Hash Fields, Hash Keys, and Hash Functions

Must-know: The hash field is the attribute the hash function reads; a single value of it is the key K; if the field is a key of the relation it is called a hash key; H(K) is the disk block address where the record lives.

$H : K \to B$

⚠️ Top pitfall: Calling a non-unique attribute a hash key - a hash key must be a key of the relation; a non-unique hash field gathers several records into one bucket and starts collisions.

Self-check: In a file with attributes name, id, phone, address, email - if you hash on name, is it a hash field or a hash key?

The K Mod M Hash Function

Must-know: h(K) = K mod M returns the remainder of K divided by M, which always lies in 0..M-1, matching the location numbers; 24 mod 10 = 4 stores and retrieves 24 at location 4.

$h (K) = K mod M$

⚠️ Top pitfall: Off-by-one counting - 24 mod 10 = 4 is the fifth location (index 4), since locations are numbered 0 to M-1; also confusing remainder with quotient.

Self-check: With M = 10, where does key 37 go, and what is the remainder rule?

Internal Hashing and External Hashing

Must-know: Internal hashing stores data exactly at the computed location (one hop); external hashing computes a bucket number, then a header table converts it to the disk block address (two hops); static hashing fixes M buckets, dynamic hashing grows them.

⚠️ Top pitfall: Treating the computed hash value as an exact disk address in external hashing - it is a bucket number, and the real block address comes from the header table.

Self-check: Why does external hashing need a structure that internal hashing does not?

Collisions and Collision Handling

Must-know: A collision is two or more distinct keys claiming the same bucket, inevitable by the pigeonhole principle; handled by open addressing (probe onward), chaining (append to the bucket's chain), or multiple hashing (apply another function).

⚠️ Top pitfall: Believing a perfect hash function eliminates collisions - no function from a large key space to a small bucket space can; good designs keep tables 70-90 percent full and plan overflow.

Self-check: Keys 11, 51, and 91 all mod 10 to bucket 1 - which technique lets them share that bucket, and how does retrieval work?

Extendible Hashing: Global Depth and Local Depth

Must-know: Bucket overflow raises the local depth and splits only that bucket, rehashing by one more bit; if d_l = d_g the directory doubles and global depth rises. Walkthrough: 32, 28, 43, 15, 48, 66 with d_g=2, capacity 2 - the split comes at 48 (bucket 00 gets 28,48; bucket 10 gets 32,66), and a later insert like 96 doubles the directory to 3 bits.

$N_{b u c k e t s} = 2^{d}$

⚠️ Top pitfall: Doubling the directory on every split - only a bucket whose local depth equals the global depth forces a directory doubling; otherwise the split is local.

Self-check: Why does inserting 96 after 32, 28, 43, 15, 48, 66 force the directory to double?

Assignment: HealthTrack

Must-know: HealthTrack: 15 marks, individual, single Word/PDF report due 30 April 2024 via Takshila; deliverables in order - problem description, ER diagram (textbook notation, pen and paper preferred), relational model, 3NF, at least five SQL queries with complexity plus DDL and snapshots, theoretical indexing choice, signed self-declaration.

⚠️ Top pitfall: Submitting a tool-generated ER diagram - tools do not use the course's notation and cardinality conventions; draw the textbook-style diagram by hand.

Self-check: What are the seven required deliverables of the HealthTrack report, in order?

Road Ahead: Indexing, Transactions, and Revision

Must-know: Next sessions: complete indexing with B+ trees, then transactions and concurrency, then revision; query optimization is out of scope; review courseware sessions 5.3 and 5.4 before the next class.

⚠️ Top pitfall: Skipping the pre-reading - the two hours of courseware turns the next session into revision instead of new material.

Self-check: Which courseware sessions should be reviewed before the next class, and what do they cover?

Exam Guidance Summary

Must-know: 3NF is always dependency preserving and lossless; BCNF may sacrifice dependencies but guarantees lossless join only via the proper decomposition method. Extendible hashing (global/local depth) is examinable - practice the 32, 28, 43, 15, 48, 66 case study. HealthTrack is due 30 April 2024.

⚠️ Top pitfall: Answering the decomposition statement without separating the two normal forms' guarantees - the sentence mixes 3NF (preserves) and BCNF (may not).

Self-check: Which property does BCNF still demand even when dependency preservation is relaxed?

Key Industry Applications

Must-know: Hashing is the standard file-organization technique for locating disk blocks; index maintenance costs storage, processing, and energy; creating a PK/FK constraint typically creates an index behind the scenes.

Self-check: Where does extendible hashing fit better than static hashing in practice?

Previous LectureLecture 10 · Storage, File Organization, and Indexing

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

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.

Prerequisite Knowledge

Previously Covered in This Subject

11.1 Quiz 2 Review: Decomposition, Dependency Preservation, and Lossless Join

11.1.1 The Question and Its Four Options

11.1.2 What Dependency Preservation and Lossless Join Mean and Why We Need Them

11.1.3 Following the Algorithm versus Decomposing by Hand

11.1.4 Student Questions and Answers

11.2 Storage Fundamentals: Why Database Access Is Disk-Bound

11.2.1 The Two Spaces: Hard Disk and Main Memory

11.2.2 The Join Example and Block-by-Block Transfer

11.2.3 Organizing Like a Filing System

11.3 Hashing and Indexing: Two Techniques for Finding the Block

11.3.1 The Shared Purpose

11.3.2 Indexing: The Book-Index Model

11.3.3 Hashing: Direct Access

11.3.4 Student Questions and Answers

11.4 Hash Fields, Hash Keys, and Hash Functions

11.4.1 The Hash Field and the Hash Key

11.4.2 What a Function Is

11.4.3 Student Questions and Answers

11.5 The K Mod M Hash Function

11.5.1 What K and M Mean

11.5.2 Worked Example: 24 mod 10

11.5.3 Buckets Instead of Exact Addresses

11.6 Internal Hashing and External Hashing

11.6.1 Internal Hashing

11.6.2 External Hashing

11.6.3 Student Questions and Answers

11.7 Collisions and Collision Handling

11.7.1 When Collisions Happen

11.7.2 The Main Handling Techniques

11.8 Extendible Hashing: Global Depth and Local Depth

11.8.1 The Idea: Address by the Last d Bits

11.8.2 Global Depth and Local Depth

11.8.3 Worked Example: Inserting 32, 28, 43, 15, 48, 66

11.8.4 When Local Depth Equals Global Depth

11.8.5 Exam Note and Practice Guidance

11.9 Assignment: HealthTrack

11.9.1 The Problem Description

11.9.2 Submission and Deliverables

11.9.3 Academic Integrity and the Self-Declaration

11.9.4 Student Questions and Answers

11.10 Road Ahead: Indexing, Transactions, and Revision

11.10.1 The Remaining Sessions

11.10.2 The Commitment Trick and Courseware Sessions

Exam Guidance Summary

Key Industry Applications

DDA Lecture 11 notes · Hashing, Extendible Hashing, and the HealthTrack Assignment

Sections Breakdown

Exam Revision Notes

Quiz 2 Review: Decomposition, Dependency Preservation, and Lossless Join

Storage Fundamentals: Why Database Access Is Disk-Bound

Hashing and Indexing: Two Techniques for Finding the Block

Hash Fields, Hash Keys, and Hash Functions

The K Mod M Hash Function

Internal Hashing and External Hashing

Collisions and Collision Handling

Extendible Hashing: Global Depth and Local Depth

Assignment: HealthTrack

Road Ahead: Indexing, Transactions, and Revision

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat