Speaker A
We're going to be looking at this new section: indexing structures for files. We have single-level ordered indexes to structure.
Overview of indexing structures for files in DBMS, covering primary, clustering, and secondary indexes with examples and access time calculations.
Key Takeaways
- Indexing structures improve file access efficiency by reducing search space using ordered pointers.
- Primary indexes rely on ordering key fields and support binary search for faster access.
- Clustering indexes organize data by non-key fields and allow grouping of related records.
- Secondary indexes provide alternate access paths on non-ordering fields and often use dense indexing.
- Understanding blocking factors and search algorithms is essential for calculating average record access time.
What the video covers
- Introduction to single-level ordered indexes and the difference between dense and sparse indexes.
- Explanation of primary indexing based on ordering key fields and how index entries point to disk blocks.
- Discussion on accessing records using binary and linear search, including formulas for average access time.
- Details on clustering indexes where files are ordered on non-key fields and how clustering fields affect data organization.
- Description of secondary indexes as additional access methods on non-ordering key fields with dense indexing examples.
- Examples illustrating block pointers, index entries, and how indexes map to data file blocks.
- Mathematical calculations for blocking factor (BFR), number of block accesses, and binary search efficiency.
- Comparison of primary, clustering, and secondary indexes with their respective use cases and implementations.
- Techniques to improve insertion efficiency in clustering indexes by reserving contiguous blocks.
- Clarification on handling multiple records with the same key value in secondary indexes and options for implementation.
Chapters
- 00:00Introduction to Indexing Structures
- 00:19Dense vs Sparse Indexes
- 00:46Example of Indexing with Numbered Records
- 01:30Primary Indexing and Ordering Key Fields
- 01:57Anchor Records and Block Anchors
- 02:22Average Time to Access a Record and Calculations
- 03:39Binary vs Linear Search in Indexing
- 04:22Primary Index Size and Search Time
- 04:51Clustering Indexes and Non-Key Fields
- 05:27Clustering Index Examples and Insertions
Full Transcript — Download SRT & Markdown
Speaker A
And this is for an ordered index file. It's small and easy to do a binary search.
Speaker A
We have a list of pointers to disk blocks. We have a dense index versus a sparse index, which is where it's non-dense.
Speaker A
And dense means that one index entry for every record of data files. And sparse is that it has index entries for only some of the search values.
Speaker A
So, this is what it's going to look like. We have multiple different ways we can index. There's primary indexing, clustering indexing, and secondary indexing.
Speaker A
So, we have these fields. And inside of these fields, they're going to be related to data files.
Speaker A
So, whatever field we specify will take us to a different data file. So, let's say we scroll down to this example right here. And instead of using names, we use numbers. Like let's say this is number one. Instead of Aaron, this is one. And
Speaker A
Adam's is five. And let's say we want to look for number four. Well, we're obviously not going to look into this next field pointer right here.
Speaker A
We don't need to look into these data values here because we know it starts at five.
Speaker A
We know since the first one starts at one, next one starts at five, it has to be in the first block. So, we're only going to be looking at the first block.
Speaker A
So, that's how that would work. It's kind of what this is showing right here.
Speaker A
Next, we have primary indexes. It's specified on the ordering key field of an ordered file of records.
Speaker A
Ordering key field is used to physically order the file records on disk. Index file consists of index entries or the index record.
Speaker A
We have the index entry. And the index entry is the primary key. And then the pointer to the disk block. So, in here on the left, we have our primary keys, and then they point to our disks.
Speaker A
Then we have our index entry, which is basically a key and value. We have one index entry, one block in the data file.
Speaker A
We have anchor records of the block, block anchor. And this is the first record in each block of our data file.
Speaker A
So, if we look at this, we can see it is ordered by name here.
Speaker A
Next, we have accessing a record. With accessing a record, we have load blocks of index files. We want to search in our index files. We have load corresponding data files.
Speaker A
There's the average time to access a record. And to calculate this, we're going to look over some examples. We have our B, which is the block size, R, which is the record size, and a little r, which is
Speaker A
the total number of records. The blocking factor, which is the BFR, is equal to B divided by R, records per block.
Speaker A
A file has a B block if B is equal to R, so the total number of records divided by B, which is our BFR. Um, I actually read that a little bit wrong, so R divided by BFR, not just B. And
Speaker A
remember, BFR is B divided by R. So, this is basically our little r divided by B divided by R.
Speaker A
And if you rewrite this, it's probably going to be something like little r times R, big R, divided by RB.
Speaker A
Now, we have a file with a B block. It's binary search to specify to find a specific record. And it needs to access the log to B block.
Speaker A
And I think this two right here should actually be down here. So, log base two B. And this is for a linear search. If you do linear search, it's going to be B divided by two.
Speaker A
Let's look at an example. This is actually a little bit incorrect. We're told how many block accesses are needed for a binary search on the data file.
Speaker A
Well, for getting our block accesses, we can use our binary search. And to do this, we're going to have our log base two B. So, I specified that here. We should also specify that this is a binary search like this. So, now
Speaker A
that we know this is a binary search, we can say that if we plug this into a calculator, we have log base two over our B. And our B is equal to our R over BFR, which is B over R. So, we can
Speaker A
essentially say that we have our log base two, and then inside of here, we're going to have our little r times our uppercase R divided by our uppercase B.
Speaker A
Given the values that we have, this is going to be 11.5. If we round this up, it should be 12. So, we have 12 because we can use binary search.
Speaker A
And then we want to use primary indexing. Well, if we have our primary index, we want to order a key field V and has nine bytes, and we have a block pointer where key is equal to six bytes.
Speaker A
Well, one index is going to be one block. And so, if we have six, we're going to have six blocks.
Speaker A
And then we need one more so that we can include this. So, that would just going to give us seven. So, it's going to take six to search our index. And that is how we look at our average time to access a
Speaker A
record. For clustering indexes, files are physically ordered on non-key fields. These are like cluster fields.
Speaker A
So, that means they're not reliant on a key. Clustering field does not require to have a distinct value. So, we're going to have a clustering index, where we have our index field and pointer. We also have one entry for each distinct
Speaker A
value of the clustering field. So, we have our index file. We have our clustering fields, and then we have our pointers after this. And this points to different data files.
Speaker A
And these fields are going to determine which data files they point to. If it's one, it'll be in this first one.
Speaker A
Two will be in this second one, and three will be in this third one. We can see that it's non-key based.
Speaker A
With insertion, we want to see how to make insertion more efficient. It's common to reserve a whole block or a clustering of continuous blocks, contiguous blocks for each value of our clustering field. Um, this figure translates into what we have
Speaker A
here. Note for number three, we can have these blocks, or we can have it kind of connect to other blocks as well.
Speaker A
Let's look at secondary indexes. These are just like primary indexes. However, if we look back at this example right here, we can see our primary index, the key, is our name. Well, we can make another primary index if we
Speaker A
were just looking at like this, and it would be the social security number. That would be like the second index.
Speaker A
So, we have two things that we're kind of filtering. Think about it like that. It provides a secondary means of accessing a file for where some primary access already exists. We have our index entry. We have the index field, which is
Speaker A
non-ordering field of the data file. We have our pointer, which is either a block pointer or a record pointer. We have our secondary key, which is the index file, and it has a distinct value for each record. One index entry for
Speaker A
each record in our data file. And then we have dense indexing, which we'll look at in a second. This is pretty dense right here, where we have these index fields, and we have these blocks, and they point to these specific blocks. We
Speaker A
can see like for the first one, it's going to point to 24. This next one points to 21. And then the third points to like six. And we can just keep going down, and these all point to different
Speaker A
things. This is very dense. So, let's look at an example that we've looked at previously. Um, if we have a linear search of here, it requires B divided by two, so that's 3,000 divided by two. So, 1,500 block accesses on average to do
Speaker A
this by a linear search. Now, the secondary index is on a non-ordering key field. So, if we have our V is nine and our P is six, only 10 is needed. So, it's smaller, and it's in order.
Speaker A
Now, let's look at our secondary index on a non-key field. Numerous records in the data file can have the same value for the indexing field. So, we have options for implementation. So, several index entries with the same key value or
Speaker A
for each one record. So, like you can think about it like we have this one right here. It's going to go to this one. We have this two, it goes to this two. Um, but we have this other one right
Speaker A
here, and it goes to this one. So, they're basically matched, and it's just we have these same index values, an
Speaker A
kind of like index right here. And then we have different slots in them where they all map to different types of like data files.
Speaker A
And then we have another one where it points to a block of record pointers.
Speaker A
So, if some K occurs and there's too many records, we can't fit the pointers, we're going to use something like this, where we have these field values.
Speaker A
We have these block pointers, and they point to blocks of record pointers. And so, these pointers, these original ones, are going to point to pointers that point to other things. So, that's how you can access it.
Speaker A
Um let's look at an example. So, we have our data file. We have student, and then we have the fact that it's ordered based on our student ID.
Speaker A
We have our student ID, name, and address. Can we implement a primary index? Uh we can. Our primary index can be the student ID. Can we intimate and implement this with a cluster? No, because it's ordered based on the
Speaker A
student ID, so it's a key. We can't do any of that. Next, we have can we do a secondary index? If so, which field?
Speaker A
Yes, we can, because if we have a first index, and we have multiple other things, we can do a secondary index.
Speaker A
So, that's done with our single level indexings. Um next, we have multi-level indexings. But these are in the notes linked in the playlist below like button. Um we're just going over more of things here, and then we also have some extra stuff with
Speaker A
like 10, 11, 12, and 13 chapters, and they can all be found in these PowerPoints. They're not mine, but my professor's. So, thank you for that.
Topics:indexing structuresprimary indexclustering indexsecondary indexdense indexsparse indexbinary searchdatabase management systemsfile indexingblock access
![[Warhammer40k] The last church; Graham McNeill. Stream-reading. — Transcript](https://i.ytimg.com/vi/x7YsEuT2B4k/maxresdefault.jpg)
