Storage, File Organization, and Indexing

10.1 Physical Storage: Volatile and Non-Volatile Memory

10.1.1 Going One Level Deeper

Until now we have worked on the user side. We built a relational schema from an ER model, we stored and retrieved data through SQL, and we normalized the schema until it was good — least redundancy, clear semantics that anyone on the team can understand, few null entries, and no spurious tuples. This session goes one level deeper, to the meat of the course: how the data actually sits in the physical storage, how it is fetched into memory, and how we can improve performance if we have to. The discussion covers storage, file structure, and indexing. RAID is not covered here because it belongs to the operating systems course; the material remains available for self-study, and the slides can be discussed later.

The ideas also apply beyond database systems, beyond programming, and in daily life. Different relations (tables) store the employees and the dependents. To answer the query we must bring the relevant data into main memory, where the processor can work on it, run algorithms on it, and finally return the answer. Behind that answer sits a lot: how the data is stored, how it is fetched into memory, and how the processor processes it to give exactly what we want. Once you see the full chain, the query is no longer magic — it is a pipeline with a known cost, and every later topic in this course (indexing, query optimization, transactions) is about spending that cost wisely.

Let us make the pipeline concrete, because it is the mental model for the entire lecture. A relational table is not stored as one big abstract structure; its rows are written into records, records are grouped into files, and files are chopped into blocks — fixed-size chunks of a few thousand bytes. Blocks are the currency of database performance: every fetch from disk moves whole blocks, never single rows. The database engine cannot read a block from the disk directly into the processor; it must first copy the block into a reserved region of main memory, and the processor works on that in-memory copy. So a query like the dependents question performs, at the storage level, three steps: locate the blocks that may contain the relevant rows, transfer those blocks from the hard disk into main memory, and then apply the select/filter logic to the in-memory data. The rest of this lecture is a slow-motion tour of those three steps.

10.1.2 Volatile versus Non-Volatile Memory

Physical storage comes in two kinds. Volatile memory loses everything the moment power is switched off; the random access memory (RAM) is volatile. Non-volatile memory keeps its contents even when power is gone; the hard disk is non-volatile. We need both kinds, and the reason is pure economics. Cache and main memory are RAM — fast, but also expensive. Hard disks and similar storage are cheaper, but slower at the same time. We want both efficiency and sound economics, so we build a hierarchy out of storage, exactly the way an organization builds a hierarchy of people: the most efficient people get the higher-level jobs, while everyone else still contributes to the organization. Storage, and many other areas of life, work the same way.

Notice what the numbers say about the professor's point: we want both efficiency (speed) and sound economics (cost), and the resolution is not to pick one technology but to combine them in layers. The most-used, most-urgent data sits in the fastest, most expensive layer; rarely-touched data sinks to the cheapest, slowest layer. When you open an application, the operating system does not copy the whole program from disk into RAM — it copies the pieces that are actually needed right now, and it keeps them there as long as they are being used. Everything else waits on disk, safe but asleep.

The hierarchy also explains a fact you have experienced daily: your computer feels fast when the data you need is already in RAM (an app you just closed reopens instantly), and it feels slow when the data must come from disk (a cold boot, or the first open of a large file). That difference is not a quirk — it is the economics of 10.1.2 in action, at every moment, on your own machine.

10.1.3 The Von Neumann Picture

All computing machines today follow the von Neumann architecture: the processor and the memory are separate. The processor asks the memory for data and then processes it. Because memory has to be organized in layers for economic reasons, some memory sits nearer to the processor and can be accessed very fast — we call it cache — and just beyond it sits main memory. You do not need the L1, L2, L3 cache details; for this discussion the important distinction is volatile versus non-volatile, and the fact that the processor acts on main memory, never directly on the hard disk.

So the picture is: persistent data lives on the hard disk, because main memory is volatile; most database data is stored at the hard disk level. We fetch data from the hard disk into main memory in chunks, the processor applies the algorithm (select, project, whatever the query needs), and the result is output. If a query asks for the students who scored between 5 and 10 in the mid-semester, we bring the blocks from the hard disk into main memory, the algorithm filters them, and the answer comes back. There is a science behind the apparent magic of storing something and querying it later, and this is where that science starts.

The picture, drawn. Picture the machine as a stack of three floors. At the very top sits the processor, which does all the thinking. One floor below is main memory (RAM) — a large, fast, temporary staging area. At the bottom is the hard disk — the huge, slow, permanent warehouse. The staircase between the disk and the memory is a one-chunk-at-a-time elevator: the disk can only send whole blocks, never single bytes or single rows. The processor never walks down to the warehouse; it only ever works with whatever the elevator has delivered to its floor. When a block arrives in memory and the processor changes it (say, an UPDATE), the changed block must ride the elevator back down to the warehouse, because the memory floor is wiped clean whenever power goes away. Every later topic in this course — buffers, indexing, multi-level indexes, B+ trees, transactions — is an engineering answer to the same elevator question: how do we make the fewest possible trips, and how do we keep the right things on the memory floor?

One real-world anchor before we move on: the hierarchy you just met is not an academic toy. Every modern laptop runs this exact stack — SSD for the warehouse, RAM for the staging area, cache for the top floor — and cloud storage follows the same tiered logic, which is why hot and cold storage tiers are priced differently. When you choose where to put a database, you are choosing how many elevator trips your queries will pay for. That brings us to the machine at the bottom of the stack: what actually happens inside the hard disk when we ask for a block? The next section opens the case and looks at the moving parts.

10.2 Anatomy of the Magnetic Hard Disk

10.2.1 The Disk Pack: Platters, Tracks, and Sectors

We are talking about magnetic disks, the HDDs of the "good old days" — many systems still use hard disk drives today. Open an external hard disk, say from Seagate or another company, and inside the case you find a pack: a stack of disks on a common axis. Each individual disk is called a platter, and each platter has two sides. Every platter surface is covered with tracks — think of concentric circles — and every track is divided into sectors. Data is actually stored in individual sectors; how much a sector can take depends on the size of the sector.

A head reads and writes the data. Some disks can read from both sides of a platter, and we can access multiple data simultaneously: when we read one particular sector, we may actually be able to read the concentric sectors around it at the same time, and the data flows through the architecture to the processor and then to the memory. The entire discussion for this session — how data is stored, how it is fetched, what processing happens once it is in memory, and how we get what we desire — rests on this physical picture.

Let us attach numbers to the anatomy, because the numbers are what make capacity arithmetic (and later the blocking-factor numericals) work. A classic sector holds 512 bytes of data, and modern "advanced format" drives use 4,096-byte sectors; the track is a ring of many sectors; the platter surface carries thousands of tracks, from an outer rim to an inner hub. Because the outer tracks are longer than the inner ones, many drives use zone bit recording: outer zones pack more sectors per track than inner zones, so capacity is not simply uniform. The head does not touch the surface — it flies nanometers above it on a cushion of air, reading and writing the tiny magnetic regions (each one a bit) that the sectors are made of.

The structure matters for one reason above all: the unit of movement is the track, and the unit of addressing is the sector. When the database asks for a block, the hardware must navigate to the sector where that block starts. The mechanism that does the navigating is what we open next.

10.2.2 Arms, Spindle, and How a Read Happens

To reach a particular sector, two mechanical movements are needed. There is an arm assembly that moves back and forth to get to the track where the data lies, and there is a spindle that rotates the platters so that the head arrives at the particular sector on that track. Even if we could know instantaneously where the data is, the movements themselves take time: the arm must move, then the spindle must turn. The arm movement is called seek, and the rotation that brings us to the sector is called rotational latency. Both are part of the access time.

These two movements are slow because they are physical. Light travels a meter in about 3 nanoseconds, but an arm assembly has mass and inertia; the fastest drives need several milliseconds to swing it across the platter. A typical desktop drive spins at 7,200 revolutions per minute — one full rotation takes about 8.33 milliseconds — and because the sector we want is usually not under the head when the arm arrives, we wait, on average, half a rotation before the data starts passing under the head.

Notice the two-phase structure of the wait: first the arm (seek), then the rotation (latency). They are sequential — the spindle can start turning the moment the arm begins to move, but the sector only passes under the head once the head is on the right track. Later, when we study indexing and file organization, every cost estimate will be a count of these mechanical waits, so get comfortable now with the idea that a "block access" is not microseconds — it is milliseconds of moving metal.

10.2.3 The Cylinder

There is one more piece of vocabulary: the cylinder. At any point in time, what we can access is a particular cylinder — the set of tracks at the same radial position across all the platters in the pack. When the arm sits at one position, it can reach one track on each platter surface at once; that whole ring of tracks is one cylinder. So: multiple disks, each with two sides of a platter, each platter covered in concentric tracks, each track divided into sectors, and the union of tracks reachable at one arm position forming a cylinder. That information is more than enough to move forward.

The cylinder earns its own name because it is the unit of no-movement access. With one arm position, the heads read all tracks of the cylinder without any seek at all — the only wait left is the rotation. Reading the ten tracks of a cylinder (five double-sided platters, say) in sequence costs one seek plus ten rotations' worth of transfer, instead of ten seeks. That is why performance-savvy layouts keep related blocks on the same cylinder, and why the operating-systems course discusses disk scheduling: it is all about turning expensive seeks into cheap rotation.

10.2.4 Student Questions and Answers

The question already anticipates the rest of this lecture: the head's "knowledge" is really an address book that maps logical positions to physical locations, and the database version of that address book is the index. Everything in 10.8–10.9 is an answer to exactly this question at the database level.

10.3 Disk Performance: Access Time, Transfer Time, and Mean Time to Failure

10.3.1 Access Time

Performance, like the performance of any employee in an appraisal, is measured through defined metrics, and for disks the central measure is access time: how much time we take to access a particular piece of data from the hard disk. To access a record we must know which sector holds it, move the arm to that cylinder, and rotate the spindle to that sector — only then, for the first time, are we at the data. Even knowing where the data is takes time to reach.

The professor described access time in words — "seek" (arm movement) plus rotational latency (spindle rotation to the sector) — and the standard reconstruction from the reference material confirms the formula. The access time is the sum of the two mechanical delays:

$$T_{\text{access}}=T_{\text{seek}}+T_{\text{latency}}$$

Here $T_{\text{access}}$ is the access time in time units (milliseconds in practice), $T_{\text{seek}}$ is the arm movement time, and $T_{\text{latency}}$ is the rotational latency, the time the platter takes to bring the sector under the head.

Why does the formula stop at these two terms? Because the professor treats the read itself as a separate stage — the data transfer time of the next subsection — and that distinction matters for how we think about cost. The access time is what you pay just to arrive; the transfer time is what you pay to collect. Some textbooks write the total read cost as $T_{\text{seek}}+T_{\text{latency}}+T_{\text{transfer}}$; the lecture's convention is to keep them separate, and we keep the lecture's convention.

The key point to remember: access time is an order of magnitude higher than data transfer time. Knowing these constraints matters for the database, because the database must be designed within them. Every scheme you will meet — file organization, indexes, buffer management — exists to reduce the number of times this 5–15 ms wait must be paid.

10.3.2 Data Transfer Time

Once we are at the sector, the remaining work is to read the data and move it to main memory. That is the data transfer time: how much time we take to read the data from the sector and transfer it to main memory. It is much smaller than the access time — access time is an order higher — which is why the movement to the right place dominates everything else.

Transfer time scales with the amount of data: it is the block size divided by the disk's transfer rate. Because a typical block is only a few kilobytes, the transfer takes a fraction of a millisecond, while the seek plus latency costs several milliseconds.

This single asymmetry explains a whole family of database techniques. Sequential scans read consecutive blocks, so the arm barely moves between blocks (one seek for many blocks). Buffering fetches blocks in bulk to amortize the access cost. Indexes exist to make the movement as short as possible. In every case, the design goal is the same: spend milliseconds on movement as rarely as you can, because the transfer part is nearly free.

10.3.3 Mean Time to Failure

Hard disks fail. A particular track may fail, or an entire disk may crash completely. Mean time to failure (MTTF) is the average time that a disk is expected to run continuously without any failure. As an illustration: suppose an external hard disk is quoted with a mean time to failure of six months — the disk is expected to run about that long before something gives.

This is not an alien topic. In any class of people who have used computers for two, three, four, or five years, a show of hands for "have you ever experienced a hard disk failure?" will draw multiple hands; if it has not happened to you, chances are very high that your system gets changed very frequently. Understand that any person can make mistakes, and the computer and hardware we build can fail as well. Respect the possibility of failures, and build resilience toward them. The professor's warning here is the seed of the next topic: because failure is a when, not an if, we design storage so that a failure does not mean lost data — which is exactly what redundancy and RAID, in section 10.4, are for.

10.3.4 Measuring Performance Like an Appraisal

The same discipline applies when you join a company: interviewers will assess what your contribution has been. Your resume should highlight quantifiable value — I improved the per-hour time, I increased the efficiency, I increased the performance, I enhanced the revenue — based on the X days, months, or years you spent in an organization. Similarly, for storage and access we define metrics up front and then measure whether our choices actually improved things: access time, the time from access through transfer to main memory, and mean time to failure are the parameters on which disk performance is judged.

The discipline has two steps, and both matter. First, define the metric before you start — otherwise "faster" is a slogan, not a claim. Second, measure before and after a change; only the measured difference justifies the change. You will meet the same discipline again in section 10.8, where indexes are judged on the same parameters — has the access time improved? Are insertion and deletion still cheap? — and again in earlier lectures, where normalization was judged by whether the schema actually got better. Metrics first, then design, then measurement.

10.3.5 Student Questions and Answers

Notice how the answer uses this lecture's own metric: the upload feels instant because the network does the long-distance transport at gigabit speeds, while the server's storage does the writes — and the server writes with enterprise drives and fast arrays that do not face the same cost constraints as a laptop. Your upload was never touching your laptop's disk at all.

10.4 Redundancy and RAID: A Course-Level Overview

10.4.1 Hardware Fails: Build Resilience

Any person can make mistakes, and the hardware we build can fail as well. Failures happen — a track fails, a disk crashes — so we respect that possibility and make our systems resilient toward it. The tool for resilience is redundancy: a proper system of redundant areas of independence, so that if there are failures we still compensate.

The word redundancy carries no apology here. In ordinary speech, redundancy is waste; in storage design, it is insurance. The principle is the same one that made you back up your project before the submission deadline: you cannot prevent the failure, so you arrange matters so that the failure costs nothing. One disk holds the data; a second, independent copy holds the same data. If one dies, the other answers. The cost of that insurance is measured in extra hardware and extra writes — and the whole art of RAID is choosing how much insurance, of which kind, is worth paying for.

10.4.2 What Redundancy Looks Like

We ensure a certain amount of redundancy by storing data multiple times. Two options: keep separate hard disks and mirror the data across them, or store multiple copies within the same hard disk. Either way the copies must be stored separately, so that one failure does not take both copies down. Depending on the choice, there are two or three mechanisms used to improve reliability — the redundant arrays of inexpensive disks family.

"Stored separately" is the load-bearing phrase. Two copies on the same disk are not redundancy in the meaningful sense — a head crash destroys both. The independence must be physical: separate disks, ideally from different manufacturing batches, often in different enclosures. That is why the mirroring and striping techniques below insist on separate physical disks, and why enterprise systems spread copies across separate machines entirely.

10.4.3 RAID Levels in Brief

RAID stands for redundant array of inexpensive disks, and there are RAID levels 0, 1, 2, 3, 4. Do not get overwhelmed by the discussion; researchers have done a very good job on these systems. If you have time, read about them, appreciate the work, and move further. RAID is not part of this course — the operating systems course handles it — and the detailed material is available for self-study.

The name itself explains the economics: the array is built from inexpensive disks, so the redundancy is affordable. Group several cheap disks into one logical storage unit, add redundancy, and you get reliability that a single expensive disk cannot offer — and often speed as well, because several disks can be read in parallel. The levels are not versions (RAID 5 is not "better" than RAID 1); they are trade-off points on three axes: capacity, speed, and fault tolerance. Sections 10.4.5–10.4.9 lay out those trade-offs with numbers, because the syllabus names the levels and the interview question "which RAID level?" is always a trade-off question.

10.4.4 Real-World RAID Advice

Whatever storage you choose — flash (SSD), HDD, or tape — it will fail sometime or other; your concern is not only keeping data safe but also accessing it, and access takes time too. The economics are yours to figure out, but it is easier to replicate: redundancy gives you faster access at the same time and downtime practically reduced to none. Consider using some form of RAID. Some hard disks already come with RAID built in; otherwise your organization has to arrange it internally or find a third-party vendor offering a rack with proper slots and redundancies in those slots — that rack may cost in lakhs. An inexpensive version works individually: for small amounts of data, use an external hard disk or redundancy within the internal disk. One good programmer can use RAID level 0, 1, 2, or 3 at the local level to get higher access speed, redundancy, and very low downtime.

Real-world: one student reported using a device with an MTTF of about one month, while others use devices rated for five years; putting redundancy on top makes the weaker device acceptable. The principle holds either way: every device fails eventually — a higher mean time to failure only postpones the problem. As one way to put it, the customer would cry less if the problem comes after 10 years instead of after 3 years, but the worry always lingers. RAID-style storage is the answer, because choosing any single device still leaves some risk.

10.4.5 The Three RAID Building Blocks: Mirroring, Striping, and Parity

The lecture deliberately left the RAID detail for self-study ("the operating systems course handles it"), and this supplement fills in that gap in the same style. Every RAID level is a combination of just three primitive techniques, and the levels differ only in which techniques they combine and how they organize them.

• Data mirroring (duplication): every block is written to two separate disks, so the data exists in two independent copies. A read can be served from either copy; a write must update both. The cost is a full 100% capacity overhead — half the raw disk space is unusable — but the payoff is complete protection against a single disk failure: if one disk dies, the other still holds every block.
• Data striping: consecutive blocks of a file are distributed round-robin across the disks of the array — block 0 on disk 0, block 1 on disk 1, block 2 on disk 2, block 3 back on disk 0, and so on. A large transfer now reads several blocks in parallel, one per disk, so throughput scales with the number of disks. Striping by itself adds no redundancy: every block lives on exactly one disk, and any failure loses data.
• Parity: for a group of $n-1$ data blocks, one extra parity block is computed by the bitwise XOR of the data blocks:

$$P=D_1\oplus D_2\oplus \cdots \oplus D_{n-1}$$

Because XOR is invertible, any single missing block can be recomputed from the rest:

$$D_i=D_1\oplus \cdots \oplus D_{i-1}\oplus P\oplus D_{i+1}\oplus \cdots \oplus D_{n-1}$$

Parity is far cheaper than mirroring — the overhead is $1/(n-1)$ of the data, not 100% — but it must be recomputed on every write, and the recovery of a failed disk involves reading all surviving disks. RAID levels 2 through 6 are essentially different ways of placing parity.

Real-world: modern disks already fail with corruption at the bit level, which is why enterprise arrays pair parity or mirroring with checksum validation — the XOR reconstruction technique above is also the basis of erasure coding in object stores and distributed systems.

10.4.6 RAID 0 and RAID 1

RAID 0 (striping only). Data is striped across all disks with no parity and no mirroring. With $n$ disks the array offers $n\times$ the single-disk capacity and roughly $n\times$ the sequential throughput, and there is zero redundancy overhead. The price: any disk failure destroys the entire array — mean time to failure actually gets worse as more disks are added, because any one of them can kill everything. RAID 0 is chosen only when performance matters more than availability and the data is re-creatable (scratch space, staging areas, game caches).

RAID 1 (mirroring only). Every block is written to both disks of a mirrored pair. Reads can be served from either copy — two reads on different blocks can proceed in parallel — so read performance improves, while writes must go to both disks and the usable capacity is half the raw space. A single disk failure is completely transparent: the system keeps running on the surviving copy, and the failed disk can be hot-swapped and rebuilt. RAID 1 is the classic choice for the database log and the operating system disks, where a small amount of critical, write-heavy data must never be lost.

10.4.7 RAID 2, RAID 3, and RAID 4

These three levels are the historical middle ground and are rarely deployed today; they matter for the exam because the syllabus names them.

• RAID 2 (bit-level striping with Hamming-code ECC): data is striped at the bit level, and several dedicated parity disks hold Hamming error-correcting codes that can detect and correct errors on the fly, not merely detect them. Because every bit of a transfer is spread across all disks, all spindles must rotate in lockstep, and a read touches every disk. The ECC machinery became unnecessary once disk controllers did error correction internally, so RAID 2 is obsolete.
• RAID 3 (byte-level striping, dedicated parity disk): data is striped at the byte level and a single dedicated disk holds the XOR parity for each stripe. All disks still rotate in lockstep, which makes RAID 3 excellent for large sequential transfers (media streaming, scientific data) and poor for small random accesses — a small update rewrites the parity block and serializes on the parity disk.
• RAID 4 (block-level striping, dedicated parity disk): data is striped at the block level, so individual blocks can be read and written independently without moving all disks in lockstep — good for random reads. The flaw: every small write updates not only the data block but also the parity block on the single parity disk, turning that one disk into a severe bottleneck. To read a block and compute new parity, the controller must read the old data block and the old parity block, then write the new data and the new parity — the famous "read-modify-write" penalty of four I/O operations per small write.

10.4.8 RAID 5 and RAID 6

RAID 5 (block-level striping, distributed parity). The fix for RAID 4's parity bottleneck is simple and elegant: instead of one dedicated parity disk, the parity blocks are distributed — rotated across all the disks, so that no single disk carries all parity writes. The array tolerates exactly one disk failure: with the surviving blocks and the XOR parity of each stripe, the missing blocks are recomputed. Capacity overhead is just one disk's worth (e.g., four 1 TB disks give 3 TB usable). The write penalty of RAID 4 remains — each small write needs old data, old parity, new data, new parity — but the load is spread across every disk. RAID 5 is the standard choice for general-purpose file servers and application servers.

RAID 6 (block-level striping, dual distributed parity). Two independent parity schemes (traditionally called $P$ and $Q$ — $P$ is XOR, $Q$ uses a Galois-field computation related to Reed–Solomon error correction) are interleaved across the disks, so the array tolerates two simultaneous disk failures — a real requirement as rebuild times on multi-terabyte disks grew long enough that a second disk commonly failed during a rebuild. The write penalty is correspondingly larger, and capacity overhead is two disks' worth. RAID 6 is the default for large archival and backup arrays where rebuild resilience matters more than write speed.

10.4.9 RAID 10 (Striping + Mirroring)

RAID 10 — also written RAID 1+0 — is nested RAID: first build mirrored pairs, then stripe across the pairs. It combines the two best-behaved techniques: striping gives the parallel throughput of RAID 0, and mirroring gives the simple, transparent failure handling of RAID 1. The array survives any number of failures as long as no mirrored pair loses both disks. The cost is the 50% usable capacity of pure mirroring. RAID 10 is the workhorse of high-performance transactional databases, where both the read throughput and the zero-rebuild-parity penalty of mirroring matter.

The capacity arithmetic is worth doing once. With four 1 TB disks:

Real-world: the grading of "which RAID level?" in an interview question is almost always a trade-off question — a database server (small critical data, write-heavy log) usually runs RAID 1 or RAID 10, a file server runs RAID 5 or RAID 6, and a scratch tier runs RAID 0.

10.4.10 Student Questions and Answers

10.5 File Organization and Record Organization

10.5.1 Files as Sequences of Records

Whenever we populate a relational schema, the data is stored in some way. The database stores its collection in terms of files, and each file is a sequence of records that is mapped onto disk blocks. A file has columns of possibly different sizes and types; one row is one record, and a file is a collection of records. This is how the database looks to us from now on: records in files, files mapped to blocks, and everything we do works in that denomination.

Keep the three levels straight, because they appear in every numerical from here on. The record is one row — one employee, one dependant, one student — with its fields. The file is the ordered collection of records that corresponds to a relation. The block is the physical unit of disk transfer — the database never moves a single record by itself; it moves whole blocks, each holding several records. A table with 300,000 rows does not live in memory as a spreadsheet; it lives on disk as a file of records packed into blocks, and every query that touches it pays in units of blocks read. That is the whole denomination the professor means.

10.5.2 Fixed-Length Records and Predictable Addressing

Suppose we know the exact size of every record in a file — every cell, every field the same size. If we also know the starting memory location of the file, we can predict precisely where any given record sits:

$$\text{address of record }i=\text{base address}+(i-1)\times \text{record size}$$

Here $\text{base address}$ is the first memory location of the file, $i$ is the record number we want, and $\text{record size}$ is the exact size of every record. The professor described this in words — knowing the start location and the exact record size lets us locate record 9, record 500, or record 1000 of a thousand-record file — and the formula above is the standard fixed-length addressing form confirmed by the reference material. Note the $(i-1)$: if record 1 sits at the base address itself, then record $i$ sits $(i-1)$ record-slots further along.

With one starting memory location, we can say where any of a thousand records resides — provided the record size is fixed and exact, not a maximum. That predictability is exactly what lets us fetch record 9 very quickly.

The formula's one condition is the whole story: the record size must be exact. The moment records vary in size, the address arithmetic collapses — we can no longer multiply our way to record $i$, because we do not know how far the previous records extended. That is why variable-length records are handled differently, next.

10.5.3 Variable-Length Records and Maximum Sizes

Real files are not exact every time: users and clients keep appending records and deleting entries, and attributes vary in size. A VARCHAR is a variable character type — the name may be up to 255, 56, or 99 characters. Even though the actual length varies, we still specify a maximum size. Why? Because knowing the maximum size of the data type lets us know the maximum size of the record. That maximum lets us bound where records can be, and helps us locate a particular record quickly — the same reason as in the fixed case, applied to the worst case.

The maximum size is a bound, not an address. With fixed-length records we could say "record 500 is exactly at 50,900"; with variable-length records we can only say "record 500 starts somewhere in this region, and never beyond this bound." Two consequences follow. First, to read a variable record we usually must read its length field first, then the data — an extra step the fixed case never pays. Second, worst-case reasoning becomes the design tool: if the maximum record size is known, the worst-case number of records per block is known, and the storage engineer can still plan block counts and buffer sizes with confidence. This is why SQL types carry declared lengths — the declaration is not decoration, it is the basis of the database's storage arithmetic.

10.5.4 Deleting and Inserting Records

Say record number three is deleted. What we would ideally like is that there is no hole in the middle: we want the space compacted, everything pushed up. That is not easy in practice. To remove the gap we must remove that space and copy everything from record three onward; internally, pointer exchanges happen as well. Similarly, if we want to insert record 11 between records 2 and 3, we must copy everything down from that point, store the new record, and fix up the pointers. Nothing here is a cakewalk, and a database system must handle it properly.

The lesson carries forward to every later topic: ordered things are fast to find and painful to update. When we meet primary indexes in 10.8, the same tension reappears — an index ordered on the search key makes lookups fast but makes every insertion and deletion a potential cascade of updates, which is exactly why the course devotes so much attention to data structures (B+ trees) that soften this trade-off.

10.5.5 Free-Space Management: Headers, Pointers, and Chains

Even when free space exists, a header keeps track of which free spaces exist. If record 3 is deleted, or record 4, the file notes that this place is free — the area is available for further overwriting. Next time an entry arrives, it may be stored in that place. Side note: when we say "delete," the entry might not be erased; it may still exist at that particular place, simply marked as available for rewriting.

To know where a new record actually starts, there is slotting, and there are pointers that tell us where things are. Free-space chains work like this: if this record is free, move to the next record, and keep moving along the chain; when inserting in the middle, we splice the new area into the chain and link it back. Pointers can be anchored at the block level as well. Sometimes multiple records are clustered within a single block — that is generally not highly recommended, though it is acceptable for joins and not otherwise.

The structure is exactly a linked list of holes. A file header records the address of the first free slot; each free slot holds a pointer to the next free slot; the chain ends with a null pointer. When a record is deleted, its slot is linked into the chain; when a record is inserted, the system walks the chain (or consults the header) for a slot big enough, splices it out, and links its neighbors to each other. The "deleted" data physically remains until overwritten — which is why the professor's side note matters, and why secure deletion tools overwrite data rather than trusting a file system's delete. Inside a database, the same idea appears again at the block level with slot directories and page-level free-space maps.

10.5.6 Heap, Sequential, and Hash Organization

Records can be organized in a few ways. In heap organization, we store a record wherever free space is found — a best-effort service. The name comes from the good old days of computer science: in C programming, malloc and free allocate memory on the fly; the heap is where things are stored at any place we find, while the stack is something else and one grows upward. The real-world heap is the same idea: like piling books — if there is space, put it there; 10 books become a heap. If a space exists, allocate it, and remove it from the free area.

In sequential organization, records are stored in order, one after another, at every point in time. From here on, much of the discussion assumes sequential storage: records sit in the hard disk one after another, and a search key helps us find a particular record. Even when we want to find someone by some other value, the search key tells us which record is which, and we still respect the way things are stored. Generally the search keys are primary keys, but as we go further, that may be different. And in hash organization, we use hashing to access particular data. (This session covers file organization and record organization; indexing and hashing as access methods are the next big topic.)

The workload-fit lesson is the one to keep: heap organization optimizes insertion (a new record just goes into any free slot — ideal for loading data fast, terrible for point lookups without an auxiliary index), sequential organization optimizes ordered scans and range queries but pays on every insert, and hash organization optimizes exact-key lookups but nothing else. A real database rarely chooses one purely; it stores the file one way (often heap or sequential) and layers indexes on top to serve the lookups that organization is bad at. That layering is the subject of sections 10.8–10.9.

10.5.7 The Record Blocking Factor

The lecture mapped files onto blocks but left one number unstated, and that number drives every storage numerical in this course: how many records fit into one block. This is the record blocking factor $bfr$. If every record has the same size $R$ bytes and a block holds $B$ bytes, the number of records per block is

$$bfr=\lfloor \frac{B}{R}\rfloor$$

The floor matters because a record may never be split across blocks in the simple case (see the next subsection) — the leftover space at the end of a block is simply unused. The total number of blocks needed for a file of $r$ records is then

$$b=\lceil \frac{r}{bfr}\rceil$$

The worked example from the indexing session applies the formula directly: with $B=4096$ bytes per block and $R=100$ bytes per record, $bfr=\lfloor 4096/100\rfloor =40$ records per block, and a file of 300,000 records needs $\lceil 300,000/40\rceil =7,500$ blocks. Every block access in every later numerical — binary search over the file, index lookup, join cost — counts in units of these blocks, so the blocking factor is the unit of measurement for database performance. Two design pressures pull in opposite directions: larger blocks mean more records fetched per access (fewer block accesses for a full scan) but more wasted space on partial fills and in main-memory buffers; smaller blocks waste less space but multiply the number of accesses.

Real-world: modern database engines use block sizes of 4 KB, 8 KB, or 16 KB — 4,096 bytes, as in the textbook example, is a real and common value — and the $bfr$ calculation is exactly how a storage engineer reasons about how many rows a page can hold.

10.5.8 Spanned versus Unspanned Records

A record has to live somewhere, and the question is what happens when a record does not fit neatly in the space left in a block. Two conventions exist.

In unspanned organization, a record is never divided across two blocks — every record is stored wholly inside a single block. If a record does not fit in the remaining space of the current block, the whole record is simply placed in the next block and the leftover space is wasted. The blocking factor is the floor formula above, and retrieval is simple: one block read locates the record completely. The cost is internal fragmentation — the small wedge of dead space at the end of many blocks.

In spanned organization, a record may be split across two (or more) blocks, with a pointer linking the continuation. This is required when a record can be larger than a block — the classic case is a BLOB, a document, or a long text value whose size exceeds 4 KB — and it eliminates the wasted tail space, because a record can always begin immediately where the previous one ended. The blocking factor becomes the apparent or average blocking factor $bf{r}^{\prime }=\lceil r/b\rceil$ computed over the file, and retrieval is more expensive: reading one logical record may require reading two physical blocks, and the second read only becomes known after the first block says "continues elsewhere."

The decision rule is practical: unspanned organization for fixed-length records that are comfortably smaller than the block (the overwhelming case in a normalized relational database, where a row is a few hundred bytes), spanned organization for variable-length records, records near or above the block size, and BLOB-style attributes. Both conventions still respect the file's mapping onto blocks — only the placement rule differs.

10.5.9 Student Questions and Answers

The answer's real point is a contrast: a database is not a flat dumping ground — its storage is engineered (relations, attributes, records, blocks, indexes), and even that engineered structure ultimately rests on the physical disk machinery of sections 10.2–10.4. The question also previews the BLOB case from 10.5.8: a file stored inside the database as a BLOB is precisely the kind of record that forces spanned organization when it grows past a block.

10.6 Metadata and the Data Dictionary

10.6.1 What the Data Dictionary Holds

There are certain data dictionaries, sometimes called metadata, that tell us what is in the database. They record the names in the relation, the sizes, the names of the different views we can have, the indexes we can create, and much, much more. Metadata also records the physical location of a relation, the number of tuples, and how things are stored. If we talk about the physical-level schema, it may include this metadata as well.

The word meta means "about": metadata is data about data. The employee relation stores the employees; the data dictionary stores facts about the employee relation — that it is called EMPLOYEE, that it has 6 attributes, that it lives at a particular location on disk, that it currently holds 300,000 tuples, that an index exists on its ssn attribute. The database itself is a program that must know all of this to function: when you issue SELECT * FROM employee, the engine does not guess where the rows are — it consults its own catalog to find the file, the record layout, and the block location. In real systems this catalog is itself a set of tables (e.g., sys.tables, sys.columns, sys.indexes), which you can query exactly like any other table — a fact that makes the "data dictionary" concrete rather than mystical: it is just tables, whose rows describe other tables.

10.6.2 Physical-Level Schema and Constraints

In the normal logical-level schema, we have not only relations but also constraints: referential integrity constraints, primary key constraints, and other constraints. We also store things that are not in the relational schema directly — for example, the rule that the balance of a particular account must be greater than 10,000. At the physical level, the metadata splits into kinds: relational metadata (relation names, number of attributes, storage organization, location, and so on), index metadata, view metadata, and attribute and user metadata — each with its own meaning when storing. There can also be references from one relation to another, because if an attribute exists in the index metadata, it must actually exist in the relation as well, and so on.

The splits are worth reading as a checklist of what a database knows about itself:

• Relational metadata — the inventory of relations: name, attribute count, storage organization, physical location, tuple count. The "table of contents" of the database.
• Index metadata — which indexes exist, on which attributes, and where their blocks live. Section 10.8 builds on exactly this: the dictionary records where the index is, so the engine can find it to find the data.
• View metadata — the definitions of named queries (VIEWs), stored so that every reference to the view can expand to its query.
• Attribute and user metadata — the per-attribute details (types, sizes, constraints like balance > 10000) and the accounts/permissions of the users who may access what.

The cross-references the professor mentions are integrity at the metadata level: the index metadata says an index exists on employee.ssn, so ssn must exist in the relational metadata for employee; the view metadata refers to relations that must exist; a constraint names attributes that must exist. This is how the catalog stays honest — the same referential integrity ideas from the relational schema apply to the schema that describes the schema. And the balance > 10000 example is the important one: business rules that are not part of the relational schema are still stored and enforced, which is why the dictionary holds constraints, not just names and sizes.

10.7 Blocks and the Buffer Manager

10.7.1 Blocks: The Fixed Unit of Storage

Whenever we talk about storage in a database, we always talk about a fixed-length unit of storage called a block. Blocks are the chunks of data we can take from the hard disk and transfer into main memory.

Everything from the earlier sections now clicks into place. The disk moves sectors; the database thinks in blocks of 4 KB, 8 KB, or 16 KB (section 10.5.7); a block holds $bfr$ records. The block is the interface between the database and the hardware: the database never says "give me record 3,457"; it says "give me the block that contains record 3,457," and the hardware delivers that whole block. This is why the blocking factor is the unit of measurement for database performance — every I/O operation is billed in whole blocks, whether you needed one record from the block or all of them.

10.7.2 The Buffer and the Buffer Manager

A buffer is the portion of main memory that is available for holding blocks. The block size stays the same; what changes is that a part of main memory is set aside to store those blocks, and that part is the buffer. A buffer manager is responsible for managing the buffers in main memory. When we want to bring something from the hard disk into main memory, the buffer manager decides at what particular place the blocks will be stored. If no space exists, it must replace existing blocks: it throws back whatever is there — and if that content has been modified, it writes it back to the hard disk properly first. This matters because the processor may have made changes inside the buffer; if we simply overwrite it, those changes are lost. So the changes are written back to the disk so they persist, and only then is the space free to be reused. Data comes into the main-memory buffer in chunks of blocks, and the same space can be reused for the next fetch.

The buffer sits at the junction of the two costs from section 10.3: a buffer hit (the block is already there) costs microseconds and no mechanical movement; a buffer miss costs the full access time of section 10.3.1 — milliseconds of seek and rotation. Database performance is, to a first approximation, the art of making the second case rare. This is also the point where the von Neumann picture of section 10.1.3 becomes operational: the buffer is the memory floor of that picture, the elevator between warehouse and processor, and the buffer manager is the elevator operator who decides what is kept on the floor.

10.7.3 Buffer Replacement Policies

Which block gets thrown out when the buffer is full is decided by buffer replacement policies — "recently used" and others, such as least recently used (LRU). We will not go into the details here before moving to indexing and hashing.

The two named policies deserve one line each so the vocabulary sticks. Recently used (more exactly, most recently used is a candidate for retention) keeps the blocks that were just touched, on the reasoning that a query working through a file region will keep touching them. Least recently used (LRU) evicts the block that has gone the longest without being touched, on the reasoning that it is least likely to be needed soon. Both are heuristics — the future is guessed from the past — and real engines tune between them (and against the query plans they can see) because no single policy wins for every workload. What matters for this course is the pattern, not the policy list: the buffer manager holds the blocks, the replacement policy decides which leaves, and both exist so that the expensive disk movements of section 10.3 happen as rarely as possible.

10.7.4 Student Questions and Answers

The answer closes the loop on section 10.1: the buffer is a reserved part of RAM, the processor works only on RAM, and the disk only ever transfers whole blocks into it. The query example reappears verbatim — students scoring between 5 and 10 — because it is the running example of the whole lecture: blocks in, filter in memory, answer out.

10.8 Indexing: Search Keys, Index Files, and Index Types

10.8.1 The Book Index Analogy

We have stored data properly on the hard disk; now, how do we access it faster? Picture an open-book examination. The question asks about B+ trees, and the book has about 600 pages. Going sequentially — page 1, page 2, page 5, and so on until page 600 — is slow. Instead, we look at the index at the back of the book: the index tells us that B+ trees are at pages 636, 637, 622, and so on. We open exactly those pages and find the material. Whether we attended the lectures or not, whether we are revising or reading in the examination itself, the index lets us jump straight to where B+ trees live. We create indexes in data the same way, so that we can access the place where the data we want sits faster — and, at the physical level, we use B+ trees to create the indexes. There are other indexes as well, but this is the mechanism of indexing.

Notice the two-part structure of the analogy, because it is the structure of every index: an index is a search structure (a way to find the location quickly — for a book, the alphabet; for a database, the ordered or hashed arrangement of entries) plus a mapping (the entry to page/block pointers). Change either part and you get a different index family, as sections 10.8.3–10.8.5 will show.

10.8.2 Search Keys and Pointers

A search key is the attribute (or set of attributes) on which we search for a particular record. A record has maybe 10 attributes; think of a record as one row of a table. Every row is denoted by a search key — for now, consider the primary key as the search key. Whenever we want to access a record, the search key says which record we mean. In the index file, there is the search key and a pointer; the pointer points to the block in which that particular data resides. These are very basic things: pay attention for the next five minutes and it is simple; miss something and it may take much longer to understand later.

An index file is a file of entries, each entry a pair — search key value plus pointer. For the employee relation with search key ssn, an index entry looks like <ssn=123456789, block 42>: the value identifies the record, the pointer says where the record's block is. The index file is smaller than the data file (one entry per record or per block instead of whole records), it is ordered (for the ordered family) so it can be searched with binary search, and it duplicates the search key values — which is why the professor says "extra effort to store them": an index is a second, smaller copy of the data's keys, kept for the sake of speed.

10.8.3 Ordered Indexes and Hash Indexes

Indexes come in two broad families. In an ordered index, the search keys are stored in sorted order — suppose the search keys are the names of the students in the class; if the index stores them in alphabetical order, we call it an ordered index. In a hash index, we make buckets: names starting with A to D go into one bucket, E to G into another, H onward into others, and so on; the bucket is then located by hashing.

The two families differ in what they are fast at. An ordered index supports range questions — "all students with names between K and M" is a contiguous run of sorted entries — which is why ordered indexes (ultimately B+ trees) are the default in real databases. A hash index answers exact-value questions — "the student named 'Kiran'" — in about one bucket lookup, but it cannot answer range questions efficiently, because related keys are scattered across buckets. The professor's bucket example (A–D, E–G, H onward) makes the cost visible: finding "Kiran" means hashing to one bucket, but listing everyone between K and M means visiting several buckets in arbitrary order. Neither family is "better"; they serve different questions, and real schemas can carry both kinds of index.

10.8.4 Primary (Clustering) and Secondary (Non-Clustering) Indexes

Every science has its nomenclature, and the nomenclature encapsulates information: saying "ordered index" to a person outside databases means nothing, but for us it means an index whose entries are stored in sorted order of the search key.

A primary index is an index on a sequentially ordered file — the index whose search key specifies the sequential order of the file. In other words, the attribute we create the index on is stored in the file in the same sequential order. If the records of the file are physically stored in that order, the index is a primary index; it is also called a clustering index.

A secondary index is an index whose search key specifies an order different from the sequential order of the file. The file is stored on the hard disk, and the records, when ordered by the search key used in the index, are not in that order in the file. A secondary index is also called a non-clustering index.

Real-world: the index-sequential file — an ordered sequential file with a primary index — is the classic construction behind many textbook and legacy database storage designs.

10.8.5 Dense and Sparse Indexes

Independently of ordering, there is the question of completeness. A dense index has an entry for every search key value that is in the file. If the search key value 101 appears, it appears in the index too; repeated entries are fine, but for all the distinct entries in the file, an index entry exists. A sparse index is the one where we do not create an index for all the entries — only some of them get index entries.

So two different dimensions: if the entries in the file for the search key — the distinct ones — all appear in the index, it is a dense index; otherwise it is a sparse index. If the search key values are stored in sequential order, we call it a primary index; otherwise a secondary index.

10.8.6 How Index Performance Is Measured

We put extra effort into indexes — extra effort to store them and extra effort to maintain them properly — so we must measure whether the performance actually improved, on the same parameters as storage access: has the access time improved? Have insertion, deletion, and overhead been managed better? On those metrics we judge the indexes, just as we measured normalization by whether the schema actually got better.

The measurement discipline of section 10.3.4 returns, now applied to the index rather than the raw disk. Four numbers matter. First, the lookup cost: how many block accesses a point query costs with the index versus without it — the index should turn "scan the file" into "a few index blocks plus one data block." Second, range-query cost: how many blocks a range query touches — clustering decides whether it is a contiguous run or a scatter. Third, the maintenance cost: what each insert and delete does to the index — updating a sparse primary index is cheap, updating a dense secondary index can be costly, as section 10.9.4 details. Fourth, the storage overhead: the index file's own blocks, which the buffer and disk budgets must pay. An index that speeds lookups but doubles the write cost on a write-heavy table may not be a win at all — which is why the professor's metric question ("has access improved? have insertion and deletion been managed better?") is the right way to judge, and why databases do not index every column by default.

10.8.7 Student Questions and Answers

This exchange is the professor's explicit check of understanding, and the terms are the exam's favorites: dense and sparse describe completeness — holes or not; primary and secondary describe the match between index order and file order.

10.9 Multi-Level Indexing

10.9.1 When the Primary Index Does Not Fit in Memory

There is a limit: the primary index may be very large — so large that it does not fit into the memory. The solution is simple and elegant: create the primary index as a file, and then create another level of index for that file as well. That is the whole idea of multi-level indexing.

Follow the logic from the last sections. An index exists to save block accesses — it lets a lookup read a handful of index blocks instead of the whole file. But the index is itself a file, and if the data file is huge, the index file can be huge too. If the first-level index runs to hundreds of blocks, searching it (with binary search) costs several block accesses of its own — and if it does not fit in the buffer, those accesses come straight from disk. The fix is recursive, and it is the same trick applied one level up: treat the index file as an ordered data file, and build an index over the index. The search then walks from the top level down — one block per level — until it reaches the entry pointing at the right data block. Search cost stops growing with the index size and grows only with the number of levels.

10.9.2 Indexing the Index

Concretely: multiple blocks exist; blocks are the chunks of data we take and transfer into the buffer. If we create an index over these blocks — say a sparse one, one index entry per block — then when the number of blocks is large, that index itself can be very large. In that case we create a level of indexing over the index, and this can be repeated. When we want to access something, rather than scanning a huge first-level index, we use the multi-level structure, which is easier and faster to access. The hierarchy is like a multi-level hierarchy in an organization: a person at a high level interacts with only three or four people, and those three or four people run the entire organization. The higher we go, the fewer levels we need to touch.

The second-level index is a primary index over the first-level index: because the first level is stored in sorted order (its entries are sorted by search key), the second level can be sparse — one entry per first-level block — and still be correct, for the same reason sparse indexes work: the value is guaranteed to lie inside the block the entry points to. The recursion stops when an index level fits in a single block; that block, the top level, is the single entry point for every lookup. Three levels are typical in practice, and the total lookup cost is the number of levels plus one final data-block access.

10.9.3 The Textbook Numerical

There is a beautiful numerical in the textbook on multi-level indexing — the book reads like a novel story; it is addictive, and you get really involved when you practice it. The point of working numbers is that something you understood intellectually ("this might work") becomes something you know works ("it actually works"). Ideally this session would have worked through it, but given the pace needed to cover everyone, it is left for you to practice. The next sessions may take up such numericals, showing with numbers how multi-level indexing impacts access.

Since the session flags this numerical as practice material and the exam guidance marks it as expected, here it is worked end to end with this course's own numbers. The file is the one from section 10.5.7: $r=300,000$ records of $R=100$ bytes, block size $B=4096$ bytes, search key $V=9$ bytes, block pointer $P=6$ bytes.

10.9.4 Updates, Deletions, and Secondary Indexes as Multi-Level Indexes

Updates and deletions with indexes follow simple rules: if you want to update the dense indexes, do this; if you want to update the sparse indexes, do that; if you have a sparse index and a deletion happens, handle it accordingly. The details follow the definitions.

The rules follow from the definitions of section 10.8.5. A dense index must add an entry whenever a new search key value arrives and remove the entry whenever the last record with a value disappears — the index is complete, so it must mirror the file exactly. A sparse index does not mirror the file: a new record only requires an index change if it starts a new block; a deletion only matters if it empties a block. In both cases the first-level index may grow or shrink, and the higher levels are adjusted only when a whole block of entries appears or disappears — which is why multi-level maintenance is cheaper than a full rebuild, and why the professor says "the details follow the definitions."

There is one more elegant point: secondary indexes are most likely multi-level indexes. Recall that a secondary index is created on a search key that is not stored in sorted order in the file. To index it, we first create one level where the entries are sorted, and then a pointer from each sorted entry to the corresponding record; from there we create an index over that level. We could have pointed directly from the index to scattered records, but that becomes a mess: when somebody changes something here, with the extra level we only need to change one pointer, which is much easier than reworking the whole index. Sometimes it is also easier to relax the design when the impact is small.

10.9.5 Student Questions and Answers

10.10 The Road Ahead: B+ Trees, Query Optimization, and Transactions

10.10.1 Next Sessions

Today's session covered how the actual data is stored in physical space, how it is retrieved when we need it, and how we can retrieve it faster through the creation of indexes. Previously we learned how to represent data; today we started at the point where data is stored and accessed. The next sessions complete the story: B+ trees and bitmap indexes; then transaction optimization — now that we understand representation, storage, and retrieval into main memory, we will look at how the processing in main memory happens to find exactly what we wanted; then concurrency, where multiple people access the same data simultaneously while each still feels like the only user, handled through transactions and concurrency science; and failure handling — checkpointing, recovery, and log files, for the failures we discussed today.

A one-line preview of each stop, so the map is clear. B+ trees are the physical form of the ordered index promised in section 10.8.7: a multi-level structure where every leaf block holds search keys in order and the tree stays balanced automatically, which is why they — not the two-level index of section 10.9 — are the workhorse index of real databases. Bitmap indexes are a different family, efficient for attributes with few distinct values (yes/no, city names) where a bit per row compresses the index to almost nothing. Query optimization is the topic of the "transaction optimization" mention — choosing, among many equivalent ways to execute a query, the one with the fewest block accesses, using the cost arithmetic this lecture established. Transactions and concurrency deliver the seamless multi-user experience of section 10.3's Q&A through the ACID properties. Failure handling — checkpointing, recovery, and log files — is the engineering answer to the MTTF lesson of section 10.3.3: failures happen, and the system must be able to rebuild its state from a log.

10.10.2 Query Optimization in the Real World

A real-world query with multiple joins, multiple filters, and two or three unions can take a lot of time, sometimes timing out. Three possibilities exist. First, query optimization will be covered in this course — but as a theoretical presentation using relational algebra, not as applied tuning for a specific database product. Second, if you use MySQL, Oracle, or similar databases, you have limited options unless you have administrative privileges and know how to create indexes properly; that is a separate discussion, where we would sit down individually to see what can be done best. Third, it may be that the data size is too huge, the complexity too high, and the processing power and main memory limited — after spending half an hour or an hour, we may conclude, in a meaningful, scientific, rational way, that the thing can only be done differently.

Real-world: applied index design on production systems usually requires administrative privileges; the science of query optimization taught here transfers, but the product-specific application is a hands-on task.

The three possibilities are three layers of answer, and students often confuse them. The science layer — relational algebra, cost estimates in block accesses, join-order choice — is what the course teaches and what you can do on any system if you understand it. The tool layer — creating the right indexes on MySQL or Oracle — needs privileges and product knowledge, which is a separate hands-on skill. And the physics layer — a dataset so large that even optimal plans cannot run in reasonable time — is a real boundary of the science: the rational conclusion is sometimes that the workload needs a different architecture (a warehouse, a bigger cluster, a different query shape). Recognizing which layer you are in is itself a skill.

10.10.3 The Project Assignment

After the mid-semester, a project assignment will be shared. The plan is to work with about 22 problem statements, with one problem statement assigned to each student. The reason: with a class of over two hundred students, if one assignment is given to everyone, ten, twenty, or thirty percent will not do it and will ask others for their work — which makes it hard to reward the people doing a good job and to incentivize by not rewarding those who are not. Individual assignments keep the work personal and fair. Whatever you are expected to do is already written in the handout — there is nothing special that will be added. You know what you are going to do; the only thing to think about is the basis on which you will approach it.

10.10.4 Student Questions and Answers

10.11 Modern Storage Architectures: SAN, NAS, and HSM

10.11.1 Storage Area Networks (SAN)

A storage area network is a dedicated, high-speed network whose job is to carry block-level storage traffic between servers and storage devices. The server does not ask for a file or a directory — it asks for raw blocks (disk sectors) by address, exactly as if the disk were attached locally. The connection can be Fibre Channel (the classic SAN fabric), iSCSI (SCSI commands tunneled over ordinary Ethernet), or FCoE. Because the network only moves blocks, the server sees LUNs — logical units — that look like bare disks, and the server's own file system and database engine run on top of them as usual.

The earlier session's question about multi-user uploads to a "storage area network" already met this idea: a SAN is the modern central storage pool, and the seamless multi-user experience is delivered by the database layer (ACID transactions) sitting on top of the SAN's block access. The advantages over direct-attached disks are architectural: storage is centralized and can be pooled and re-provisioned without touching servers; capacity grows by adding disks to the array without shutting anything down; and backup, snapshotting, and replication are performed on the array itself rather than by each server.

Real-world: SAN arrays are where enterprise databases actually live. The RAID discussion of 10.4–10.9 happens inside the SAN — an enterprise array is a box of dozens or hundreds of disks wired into RAID groups, with the SAN fabric exposing those groups to servers.

The two things to notice about a SAN are what it moves (raw blocks, not files) and what the server sees (bare disks, not folders). Because the traffic is addressed by disk addresses, the SAN fabric is built for latency and throughput at the block level — and because ordinary machines on the office LAN are not part of that fabric, SAN traffic is invisible to them. Every design consequence below — the LUN abstraction, the dedicated network, the low-latency requirement — follows from that one choice: blocks, not files.

10.11.2 Network Attached Storage (NAS)

A NAS is a storage appliance attached to the ordinary local-area network, serving files, not blocks. Clients talk to it with standard file-sharing protocols — NFS on Unix-like systems, SMB/CIFS on Windows — and the appliance runs its own file system and hands out shares (directories). A NAS device is in essence a small, dedicated file server with its own operating system, and to a client it looks like a remote hard disk with folders.

The SAN-versus-NAS contrast is a single crisp distinction that interview questions love: SAN serves blocks over a dedicated storage network; NAS serves files over the regular network. SAN traffic is addressed by disk addresses and is invisible to ordinary machines on the LAN; NAS traffic is addressed by file paths and is a normal network citizen. Their roles follow: NAS for file sharing, home directories, backups, and web content, where whole files are the unit of work; SAN for databases and virtual-machine disks, where low latency on random blocks is everything.

The table's first row is the whole story, and the rest of the rows are its consequences. A database engine wants to manage its own blocks, its own buffering, its own ordering — that is what SAN gives it, by handing over raw LUNs. An office full of people editing documents wants folders and files on the shared network — that is what NAS gives it, by handling file semantics inside the appliance. The "when to pick which" rule: if your workload thinks in files, use NAS; if it thinks in blocks, use SAN.

10.11.3 Hierarchical Storage Management (HSM)

Hierarchical storage management automates the one economic insight that opened this lecture — faster storage is expensive, cheaper storage is slow — by treating the whole storage estate as a tiered hierarchy and migrating data between tiers automatically according to how often it is accessed. The typical hierarchy: fast SSD or disk for active data, slower disk for warm data, and tape or optical media for cold, long-term data. A policy engine tracks access frequency; files that have not been touched for a defined period migrate down a tier, and files that become active again migrate up. A popular earlier example makes the point: satellite data that must be retained for a year or two is precisely the kind of cold data HSM pushes onto tape, which the lecture already flagged as reliable but slow — HSM is the machinery that hides the slowness, because only the rarely-needed data goes there.

The subtlety that makes HSM work: migrated files may leave a small stub (a pointer record) behind in the active tier, so applications still see the file name in the directory; the first access to a stubbed file triggers an automatic recall from the lower tier. The user experience stays the same; only the latency of a cold access changes. HSM is the file-level cousin of the memory hierarchy discussed in 10.1 — same economics, same tiering idea, applied to secondary storage instead of main memory.

Real-world: HSM-style tiering is everywhere in modern storage — Amazon S3's storage classes (standard, infrequent access, Glacier), Azure's hot/cool/archive blobs, and tape libraries at archives and research institutions are all the same policy-driven tiering idea, with the tape tier typically the cheapest and slowest.

The connection back to section 10.1 is the point of the whole subsection: the hierarchy that began with registers, cache, and RAM continues, at the file level, with SSD, disk, and tape — and HSM is simply the policy that moves data between the lower tiers automatically, exactly as the buffer manager moves blocks between disk and RAM by policy (section 10.7.3). The stub mechanism deserves the attention: it is what makes migration invisible. Users and applications see the same directory, the same names, the same files; only the response time of a cold access betrays where the data actually lives. That is the same transparency bargain the whole storage hierarchy has offered since section 10.1: the layers do the moving, and the application never needs to know.

Exam Guidance Summary

• What is in this course: storage and file structure (volatile versus non-volatile memory, hard disk anatomy — platters, tracks, sectors, cylinders, arms, spindle — access time, seek time, rotational latency, data transfer time, mean time to failure), record organization (files, records, blocks, fixed and variable-length records, deletion and insertion, free-space chains), metadata, buffers and the buffer manager, indexing (search keys, ordered and hash indexes, primary/clustering versus secondary/non-clustering, dense versus sparse), and multi-level indexing.
• Syllabus supplement (sections 10.4.5–10.4.10, 10.5.7–10.5.8, 10.11): the detailed RAID material (mirroring/striping/parity; RAID 0, 1, 2, 3, 4, 5, 6, 10 with capacity arithmetic and fault tolerance), the record blocking factor $bfr=\lfloor B/R\rfloor$ with the 300,000-record worked example, spanned versus unspanned records, and the modern storage architectures (SAN versus NAS block-versus-file distinction, and HSM tiering). The live session left RAID to the operating systems course, so this material is supplementary rather than lecture-derived.
• What is NOT in this course: the live session's RAID overview pointed to the operating systems course; the detailed RAID supplement (10.4.5–10.4.9) fills that self-study gap and may be expanded further.
• Exam note: expect the classic numerical on multi-level indexing — the one in the textbook that "reads like a novel." Practice it with real numbers; the next sessions may work such numericals in class. Section 10.9.3 works the full numerical with this course's own numbers (300,000 records, 4,096-byte blocks, 100-byte records: $bfr=40$, $b=7,500$, one-level index in 28 blocks giving 6 accesses, two levels giving 3 accesses against 13 for plain binary search) — rework it with different block sizes until the pattern is mechanical.
• Exam note: be ready to distinguish dense versus sparse (about completeness — holes or not) from primary versus secondary (about whether the index order matches the file order). This distinction was an explicit check of understanding in the class.
• Exam note: the open-book analogy applies to you as well — use the index of any book to jump to the exact pages (B+ trees at pages 636, 637, 622, for example) instead of scanning sequentially; that is precisely how indexing works in storage.
• Exam note: the blocking-factor arithmetic in 10.5.7 is the unit of measurement for every storage numerical — remember the floor for $bfr$ (records never split) and the ceiling for $b$ (a partial block still exists).
• Exam note: vocabulary questions are common on the disk anatomy — track, spindle, sector, cylinder — and on the metrics — access time, seek time, rotational latency, data transfer time, mean time to failure — so be ready to define each and to explain why access time dominates transfer time.
• Study advice: write down everything you do not understand — track, spindle, sector, cylinder, everything — and ask. Better to say "I don't know" once than to remain ignorant for a lifetime.
• Study advice: attention is your most valuable asset; sessions assume you have already gone through the prepared material, so review before the session.
• Exam note: the project assignment comes after the mid-semester. There are 22 problem statements, one per student; all expectations are already in the handout, and the only thing to think about is the basis on which you will do your work.
• Career note: performance in this course is measured the same way companies appraise employees — define the metrics first (access time, transfer time, MTTF; insertion, deletion, overhead), then measure whether your design improved them. On your resume, quantify contributions: improved efficiency, performance, revenue, over X days, months, or years.

Key Industry Applications

• Real-world: the anatomy of a magnetic disk (platters, tracks, sectors, arms, spindle, cylinder) is visible in any external hard drive, e.g., Seagate drives.
• Real-world: Dropbox-style fast uploads combine network improvements (1G to 5G and beyond) with heavy servers that do the real processing — a return to the client-server model of the early 2000s, now called the cloud.
• Real-world: storage area networks and multi-user enterprise systems rely on database administrators, concurrent transactions, and ACID guarantees (atomicity, consistency, isolation, durability) so every user feels like the only one.
• Real-world: SSDs (flash) — the pen-drive technology of 15 to 20 years ago — now ship as the storage of modern laptops; they are an order faster than HDDs because there are no spindles or tracks, and access needs no seek or rotational latency.
• Real-world: tape drives are the reliable, long-duration archival medium for demanding use cases such as keeping satellite data for one or two years, with the trade-off of slow search — which is why HSM (10.11.3) moves such cold data to tape automatically and recalls it by stub.
• Real-world: RAID racks from third-party vendors (costing in lakhs) and local RAID 0–4 setups give higher access speed, redundancy, and near-zero downtime; even devices with a one-month MTTF become usable when redundancy sits on top.
• Real-world: dump-style storage — IPFS (the Interplanetary File System) and data lakes — pushes data in and demands mining effort later, in contrast with the structured science of database storage.
• Real-world: query tuning on MySQL or Oracle typically requires administrative privileges; the optimization science taught theoretically (via relational algebra) transfers, but applied tuning is a separate, hands-on exercise.
• Real-world: hardware firms such as Seagate and Nvidia decide the physical details — how many arms, how many platter sides — while the computer scientist's model of seek plus rotational latency stays unchanged.
• Real-world: the blocking-factor arithmetic of 10.5.7 is exactly how storage engineers size pages in modern engines (4 KB, 8 KB, 16 KB blocks) and how enterprise SAN arrays (10.11.1) are configured into RAID groups for databases.