大家好，数据结构与算法这一讲我们开始第十一章索引的学习， Hello, everyone, let’s start chapter 11th index in Data Structure and Algorithms today.
今天我们首先介绍一些基本概念，然后介绍线性索引和静态索引。 Firstly, I will introduce some basic concepts, and then introduce linear index and static index.
索引是主要针对我们的外层文件系统特别是数据库的系统而进行的。 Index mainly aims at outer file system, especially data base system.
在我们的这些数据库系统里面，我这个记录存在文件里面，因为文件它本质上是一个线上的结构，如果要查找里面的某一个记录，你得从文件头到尾，挨个去找，然后我们知道去找访外的速度是非常非常慢的。 Notes are stored in files in our data base system, and files are a linear structure in substance, so when we want to search a note, we have to search one after another form begin to end of the file, which, as we all know as external storage access, is very slow.
这样的话我们要想如果经常的话查找的这些记录，我们是不是能够建立有效的索引。 Thus if we want to search these notes quite frequently, I think whether we could create efficient index.
特别是对这个记录它的一个关键码的东西也就是说能够唯一的区别这个记录与它的这样的一个主码信息，我们就希望能建立这样的索引。 Especially for the key code of a note, namely the main code information which can separate the note from other ones uniquely, it’s expected we can create efficient index.
这个主码是数据库里面的一个记录唯一标识符。 The main code is the unique identifier to a piece of note in the data base.
我们在定义这文件数据库的时候我们对一个数据库的表我们都要指定它的唯一标示的这么一个主码。这个主码它显然是经常用来检索的。 So when we define a file data base, we should point out a unique identified main code for every table of the data base.
辅码是数据库里面它可能是也经常查，但是可能这个记录它在辅码域并不是唯一的，我们就是可能它这个域建立一个辅码的这样的一个信息，也就是说我对这个域我要进行它有效的索引。 As for sub code, it can often be searched, but note are not unique in sub code field, so we may create some information like sub code for the filed, that is, we will index this field efficiently.
这索引它的本质，其实是关键码和它这个记录在顺序文件的存住地址的一个映射 The essence of index is a map between key code and the store address of its note in sequential file.
我们这个关键码和这样的一个地址其实我们就是把它当作一个key pointer 这样的一个二元组 So we regard the key code and the address as a dualistic pair as key pointer.
然后我们的这样的一个索引的信息就是由若干的二元组来 And then the information of an index is composed of some certain dualistic pairs.
索引是数据库以至一些检索系统里面它最关键的一个技术。 Index is the most essential technology in data base and even in some search systems.
基于这个索引技术我们才能够进行非常高效的这样的检索。 And only based on index technology can we search very efficiently.
而且我们很多时候的插入删除等等，也是基于索引来进行的。 And many operations, such as insertion and deletion, are all based on index.
索引文件我们可能可以有很多，单单我这个主索引文件，就是说，对应于主码的文件应该只有这样一个的索引文件。 There could be many index files, but the main index file, the file attached to the main code, should be alone.
但是如果是我对很多的这个就是非主码的域，也就是一些属性域我都想经常进行查找，我都给它建立这样的索引的信息，就可以建立很多个这样的索引文件。 However, if we want to search in some sub code fields, which are not attached to the main code, we can create such index information, and we can create many such index files.
但是索引文件你建多了以后,，我将来这个主顺序文件它有记录的这个插入删除等等的这样的更新的时候你这样的索引文件也继续相应的更新，我们也会带来一些额外的操作的代价，所以我们并不是越多越好，这要根据实际的应用和需求来建立。 But if we create too much index files, we will have to renew the index files accordingly whenever we renew the main ordered file, inserting or deleting, which will bring cost of extra operations. So more indexes don’t mean better, they should be created according to actual application and need.
么我们在建立的时候，也有两种索引，就是稠密和稀疏。 And there are two kinds of indexes--thick and sparse ones.
稠密索引就是,如果这个主数序文件如果没有排序，我这个记录我就是每一个记录我都要在这个索引文件里面有一个key point的对来对应到它。 Thick indexes mean when we don’t sort the main order file, every note need a key point corresponding to it in the index file.
如果是排序的情况下，我可能就是若干个连续的这样的记录，它们是存在一个磁盘块里头的，这样的话，我只需要保存这个磁盘块里面的最大，或者是说所有这种磁盘块里面的它的这个最小的记录，它的key point这样的值我就能够对这个整个主顺序文件我都有所了解。我在查找的时候，我都能够找得到相应的记录。这就是稀疏索引。 If we have sorted the main order file, we get some continuous notes stored in the some disk block, so we can know the whole main orser file by merely storing the key point of the biggest or smallest note in the disk block. This way, we can find the note when we search it. And this is called sparse index.
我们再来看，线性索引结构，这个线性索引结构，它主要是哪个对这样的一个数据库的这样的主顺序文件我所有的这些记录我都建立一个这种key point的这样的索引域。 Now let’s learn linear index structure. It means we create a key point index field for all notes of main order files in a date base.
我建立了这个线性的索引文件，我其实是根据这个它的这个key值在这个索引文件里面我们进行了一个排序。 When we create a linear index file, we sort the index files according the key value actually.
我们可以看到原来的这个主顺序文件它并没有排序，我要找的时候只能挨个找。我建立了索引以后，我在索引块里面我就可以是二分找，不需要挨个找了。而且我找到以后，我就直接通过它的这个point的指针域马上就找到它对应的这个记录的位置，然后把这一堆信息给它找出来，因此它是非常的便捷的。 As we can see, the original main order file wasn’t sorted, so we can only search one after another; if we create the index, we can do binary search in the index blocks, other than one after another. And once we find it, we can find the correlative note through the pointer field of its point, than we can get all information of it. So it’s very convenient.
我们有了这样的一个线性的索引结构的话，我们就能够加快对这个数据库，主顺序文件的领取的一个速度。 So if we have a linear index structure like this, we can get the main order files in the data base much faster.
线性索引它可能本身也很大，就是我整个的索引文件都特别大，我不能够一次读到内存里面，我如果是说我要找这个外存的这个主文件里面的信息，我光这个索引文件我就读半天，这个情况我们就想，这不是这个索引块它本身也太大，我是不是还建立这个再上一层的索引，就对索引的索引，就建立了这样的多级的索引结构。 The index itself, namely, the whole index file, will be too large. If we can’t store it in the RAM at a time, when we want to search the information of a main order file in the ROM, we must spend amounts of time to read the index file. And then, we believe that the index itself is too large, and we decide to create the index of index, the upper floor index. This way, we create a multilevel index structure.
当然你要建立这样的一个多级的索引结构，它相应的在主文件里面的更新的时候，一级索引要更新，可能二级索引它也是同时需要的更新。它的更新的这样的考虑，要更复杂一些。 Of course, if you create such a multilevel index structure when you renew a main file, the correlative first index have to be renewed, maybe the second index need renewing, too. And it’s a bit more complex to think about the renewal.
我们来看一个二级索引的例子，假设我们一个外存的磁盘块，也就是说一次IO的这么的一个单位是1024字节，我们这样的一个key point的索引对，我们需要8个字节。这样的话，我们一个磁盘块可以容纳128条这样的key point的索引记录。如果我们一个数据文件它是一万条这样的情况，我们通过计算知道我总共是需要79个这样的磁盘块才能够把这些记录建立了一个密集的索引。 Let’s take a two-level index for instance. Suppose there is a disk block in the ROM, the unit of an IO is 1,024 bytes, and a key point index pair needs 8 bytes. So a disk block can accommodate 128 such index pairs of key point. If a file contains 10,000 such things, we know that we need 79 disk blocks to create a thick index for those notes.
79个磁盘块的这样的一级索引，意味着如果我是对这个主顺序文件里面某一个记录我需要读它的话，我首先读这个一级索引就要79次访外。这是一个很浩大的一个代价。 The first index contains 79 disk blocks, which means that if we need search a piece of note in the file, we have to search in the first index for 79 times. The cost is too enormous.
我们就想，我是不是可以再对这个索引块我再索引一层，我用一个磁盘块就可以把它放进去？这样的话，我们就只需要先找到这个二级索引，这里，然后我通过二级索引找到一级索引里面相应的位置，这样的话，我们在索引块里面只需要找两次就找到了。 Then we decide to index the index block, and the second index can be stored in one disk block. This way, we merely need to find out the second index, and find the correlative position in the first index, which means we just need to search in the index for 2 times and get the result.
比你刚才平均情况下，你可能会要找大约是40次你才可能找得到。就有很大的提升。 Compared with the average cost in the former one, in which you have to search for about 40 times to get your result, the new way improves a lot.
我们来看这个二级索引的一个例子。这个一级索引其实它建立的是一个密集索引的这样的一个结构，就是说每一个记录项,都对应到一个这样的索引域，然后这个二级索引，它相对来说它就是一个稀疏索引，因为它其实只需要记录譬如说这一个整个磁盘块里面最小的个是1，第二个磁盘块最小的是200003，对应的就是每一个块我只需要索引它的最小的一个，因为你每一个索引块本身它都是有序的。我能够通过对这个二级索引的能够很准确的定位到一级索引里面，它是在个磁盘块里面。 Let’s analyze two-level index. The first index is actually a thick one, that is, every note is corresponding to an index field; and the second index is a sparse one relatively, because it just index the smallest value in each disk block, for example, 1 in a certain block and 200,003 in the next block. Because an index has been sorted already, we can position our target exactly in the first index in the disk block through the second index.
然后，我们来看一下对我们刚建立的这么的一个索引块，我们是二级索引的这样的一个结构。 Then, let’s analyze the index block we created just now, it is a second index structure.
我们来看一下我们对这个二级索引我来怎么找到这个2555这样的一个记录。首先我就是在这个根一级的二级索引里面我去用二分的检索方法来找，我找到说我相应的这个记录它可能是2003所在的这样的一个线性索引，就是一级索引这个框里面。然后我就是指到这一块。然后在这一块里面，它也是一个有序的。我还能够进行一个二分检索，然后找到它相应的这样的一个位置。 Let’s see how this second index find the 2,555 note. Firstly, we do binary search in the root level—second index, and what we find may be a linear index containing 2,003, which is a block located in the first index. Then, because the block itself is sorted, we can do binary search in this block, finally we get the correlative position.
这个位置，它就对应到我们这个我们外层的这个组顺序文件里面的这个地址块的这样的一个位置。然后我们把这个位置里面所存的这几记录的所有信息，就是除了这个key以外，它还有一些属性于的信息，就是说譬如说我们这个key当作它这个是工号的话，我相信到这后面还会有譬如说它的姓名呀，工资呀，它的教育背景等等的这些信息。含有这样一类的索引的结构，我们就把它称为静态索引。 This position is corresponding to a position of outer order file. And all information about those notes are stored there, that is, besides that key, there is also some correlative information, for example, if the key refers to a job number, we believe there must be his/her name, wage, educational background and so on. And we call the structure containing this kind of index static index.
这个静态索引它也是跟我们的刚才这样的多级的这个先显索引是一样。我们主要是就是在这个文件它一抽离的时候，我就开始就给它建立好了它的这个更新其实是非常不方便的。 The static index is the same as the multilevel index mentioned above. And it’s very inconvenient to renew the index the moment the file is pulled away.
我们有一些变种的这些技术可以让它可以支持一些小的对象。但是不能支持比较大的更新。 There are some varietal technologies suitable for tiny objects, but they cannot be used to renew bigger ones.
在这个静态索引里面，有一种这个索引叫作多分树。这个多分树它其实跟我们原来BST这个结构它有一些类似。多分树它相对于BST不一样，它更适合于外存。 In the static index, there is an index called multi branch tree, which is similar to the BST structure we learned before, but they are not the same, because the multi branch tree is more suitable for ROM.
我们能够提高这样的检索效率，就是说它能够大大的减少这个访外的次数。我们来看这个多分树的这个树形。 So we can improve the efficiency of retrieval, that is, we can decrease visit times. Now let’s see the shape of the multi branch tree.
就是我们原来假设有这么多个这样的关键码，这个主码。 Suppose there are many such key codes and main code.
它根据这个BST这样的一个有序的结构我们已经建立了一个索引的结构。 And we have created an index structure according to the vertically sorted structure of BST.
如果说是一个二叉树的话，我们每一个这个结点都对应到外存的一个页块，这样的话，我总不是有这个6层的这样的访外我才能够找到我的可能的记录单。 So if it’s a BST, every node should be corresponding to a page block in the ROM, this way, I don’t have to search for 6 levels every time to find the possible notes.
如果我快的话，平均情况下，我也是接近这个6的这样的一个访外的这样的一个次数。 If it’s fast enough, on average, the visit cost is near 6 times.
如果是在这个外存页块，也是我们前面的一个例子我们一个页块可能我能存1024个字节，而且它其实是能存128对的这样的索引对。 In the page block, as is mentioned in the instance above, I may store 1,024 bytes, and actually, I often store 128 such index pairs.
这种情况下，我就不要用这个2叉的这样的结构。我这里面尽量多分一些的这样的索引的这样的记录。然后我把这个譬如说这里相连的7个结点，给它并起来。 Under this circumstance, we don’t need such BST structure, and we try to allocate as more indexes for such notes, then, for example, we put 7 adjacent nodes together.
然后，我就变成了一个8分树。这个树，它有8个分支。我们底下也是这个相连的这个3层我们都给它并起来。我们就变成了一个这样的8分树的这个结构。 Then, we get a 8-branch tree, and there are 8 branches on this tree. So we put the 3 bottom levels together and get the 8-branch tree structure.
我们在检索的时候，譬如所我要检这里面的某一个这样的结点，我先通过这个跟这一个页块，然后找到我相应的它指向说在下一层是个页块，我再找到这个页块里面的这个对应的这样的一个key point 的这样的一个索引项。 When we do retrieval, for example, to search a certain node, we find a page block firstly, and then get the correlative block it points to of the next level, at last, we get such a correlative index of the key point in this page block.
然后，这个索引项我能够指向这个我们的外存的这个组顺序这个文件，然后这个组顺序的这个文件里面的某一个具体的这样的一个记录块，然后我们把这个数值读出来。 Then, the index points to the file in the main order file in ROM, and then a certain concrete in the main order file, and then we get the value.
我们注意，这里面它其实访外主要是分为3次。前两次它是访问这个索引数的这么一个过程，还有一次，注意我们找到这个索引项就是这个key point以后，还需要访问这个组顺序文件里面的具体存放这个它的数据域的这个的这样的一个数据块。 So please pay attention, there are 3 steps to do our visit. In the first to steps,we visit the indexes, and in the last step, after we find the index, namely, the key point, we still need to visit the data block in the data field in the main order file.
所以这是3次，我们可以看到这些关键码，它们其实还是一个在深搜的类似于这个中序的这个访问顺序下，它还是有序的这么一个结构。多分树的一个应用就是指早期的这样的一个磁盘管理文件系统。叫做ISAM，它是对于种经常要进行插入，删除的这样的平方操作的这样发行的数据库文件来设计的。在当年也是起到了非常重要的作用。它其实是采用了一种多级索引。 So there are 3 steps, these key codes are actually under the visit order of BFS, similar to internal-ordered visit, it’s a sorted structure. An application of multi branch tree is ISAM, an early disk file management system, it’s designed for the data bases on which square operations such as insertion and deletion are operated frequently. It helped a lot then, and it used a kind of multilevel index.
这个多级索引它分为这个主索引，然后柱面索引，以及磁道索引这3层。 Multilevel index is made up of main index, cylinder surface index and track index.
后面，我们有基于b树的这样的一个VSAM的技术，取得了ISAM, 我们稍微看一下ISAM这么的一个索引结构的一个示意。 And then, we get ISAM through VSAM, which is based on B tree. Let’s learn the index structure of ISAM slightly.
我们这个静态索引，最上一层这个C0,这一块是主索引它对应到就是我们这里有若干个分区，然后这个分区里面它有这样若干个的这样的柱面， The topmost level of the static index, C0, is main index, correlatively, there are many zones, and there are many such cylinder surfaces.
然后这个柱面的话，譬如说我们看这个柱面C1然后它对应到这个磁道里面的这个若干个这个索引块就是这个是T1,T2到T7，这里面前面是对这个记录的这个存放，然后这个后面就是分割出一些溢出区。这个溢出区主要是我们在插入的时候，如果满了的话我们可以暂存在溢出区。 If the index blocks in tracks which cylinder surface C1 is corresponding to are T1, T2 and T7, notes are stored there, and after them there are space for overflow files. When we do insertion, if the indexes are filled up the extra files can be stored in the space temporarily.
而且在这个相应的磁道一块，它有指向这个溢出区的这样的一个指针。这样的话我们就使得这个整个记录文件它的插入删除相对来说比较的灵活。 And in the correlative track, there is a pointer pointing the space for overflow files. This way, it’s relatively flexible to operate insertion and deletion on the whole file.
这是后面的第二个柱面和第九个柱面。它的相应的访问的信息。我们可以看到这些数据已经是经过排序了的。 These are the second and ninth cylinder surface and their correlative visit information, as we can see, these data are sorted already.
最后个大家留下思考就是我们在什么情况下需要建立这样的二级索引，甚至我们可能要建立三级索引这样的一个多级的索引的结构。 At last , I have a question for you--when do we need to create such two-level, three-level and even multi-level index structure?
另外，就是我们多分树的节也就是说它的这个子结连的个数，也就是说我们说的对应的几个叉。我们是怎么样来进行划分的？ Besides, the branches of multi branch tree—the number of its child nodes, that is the correlative branches, how do we partition them?
谢谢大家。 Thank you.