大家好，今天我们学习数据结构与算法第十章，检索， Hello everyone, today we learn the data structure and algorithm to the tenth chapter, retrieval.
检索在计算机中是一种非常重要的操作，它经常跟用户打交道 Retrieval is a very important operation in the computer. It often deals with the users.
因为用户经常要查找符合某一些关键码值的相关内容， It is because users often need to find related content in accord with some key value.
除了这个关键码值以外，这个值它的后面带着一堆属性。 In addition to the key value, the value behind it takes with a bunch of attributes,
常用的检索方法，有基于线性表的检索，还有对集合的检索， Commonly used retrieval methods include the retrieval based on linear table, along with the retrieval of the collection,
特别是有一类对于检索的性能要求特别高的检索 Especially with a kind of retrieval with particularly high requirements for the retrieval performance.
我们希望在跟数据规模无关的这么一个时间内能够响应， We hope to respond in such a time that has nothing to do with the data scale.
也就是常数时间内能够响应， That is, respond in constant time.
就是散列的方法， That is the method of the hash.
在我们日常用的搜索引擎当中，它对我们的关键码进行了散列的索引， In the search engine of our daily use, it is to our key for the hash index, it indexes the hash for our keys.
然后我们能够进行散列的检索， Then we can index the hash.
检索其实是一个(key,value)对的一个查找过程 Index is in fact a process of finding (key,value).
对于这个(key,value)对的查找， For finding (key,value),
首先是找到符合我的关键码key的这么一个记录， Firstly we need to find the record in accord with the key,
这个记录之后的一堆属性，我要把它找出来， We have to find the attributes behind the record,
检索的效率它是非常重要的，特别是对于一些大数据量的情况下， Retrieval efficiency it is very important, especially for some large amount of data,
例如，搜索引擎，它所面临的成千上万的关键词的检索需求， For example, a search engine, it faces the tens of thousands of keywords retrieval demand,
以及后端，几百个亿的网页的存储量， and the back-end of storage, hundreds of billions of web pages.
我们怎么样有效的去把它检索出来是非常重要的操作， Then how we can effectively retrieve it is very important for the operation.
我们往往可能需要对这些相应的数据进行特殊的存储处理， We may need to do special storage processing for the corresponding data.
这些存储处理如果小规模的话，我们可以有些预排序等简单的处理方法， These storage processing, if small, we can have some simple processing methods, such as preliminary sorting.
如果是大规模，我们可能需要进行一些特殊的索引 If it is large, we may need to do some special indexes.
特别是，我们可能要建立这样的散列的索引， In particular, we may have to establish such a hash index,
提高检索效率有哪些方法， What are the methods to improve retrieval efficiency?
首先，如果这个数据是经常要进行检索的， First of all, if the data is often to be retrieved,
对于一堆无序的数据，它的检索效率就不是很高了 For a heap of disordered data, the retrieval efficiency is not high.
对于没有任何信息的一个索引，我们就只能挨个找， For an index without any information, we have to turn to find,
因此，我们要建立这样的预排序， Therefore, we must establish this presort,
排序了以后,对于这样的查找过程， After the sort, for the search process,
我就可以利用它的有序性进行一些更高效的查找， I can use the order to do more efficient lookup,
比如说，二分的检索， For example, binary search,
另外，如果我们经常要反复查找，我可能要建立一些比较高效的检索， In addition, if we often have to find again and again, we may want to set up some more efficient retrieval,
这个索引是一些辅助的信息， This index is some auxiliary information,
这些信息需要有一些辅助的空间 This information need to have some auxiliary space.
在这些空间的辅助下，我们能够提高检索的效率， In help of this space, we can improve the efficiency of retrieval,
当然，建立索引以后，我们同时也带来了维护的一些麻烦， Of course, after the index, some trouble of maintaining is also brought at the same time,
我们要保持这个数据的一致性， We must keep the data consistency.
特别是当我们的主数据改变的时候，索引的数据也要进行相应的修改 Especially when our master data changes, the index data also must carry on the corresponding modification.
对于常用的一些检索的需求，特别是，数据量特别大，用户量也特别大的时候， For the demand for some commonly used retrieval, in particular, when there is a large quantity of data and users.
就有一种非常好的一个检索技术，就是散列， There is a very good a retrieval technology, that is the hash,
散列本质上也是一种非常高效的索引技术， The hash in essence is a kind of very efficient indexing technology,
它把这个数据，根据它的key，映射到一个表里面， It maps the data, according to its key, to a table inside,
这个映射过程，就是一个O(1)的时间代价， This mapping process is a O (1) time cost
我们在找的时候也是用这个函数把它找出来， We also use this function to find it out,
它也是个O(1)的过程， It is also a process of O (1),
散列在检索上非常高效的，但是它只针对一个key来进行， Hash is very efficient in the retrieval, but it only for a key,
如果要对散列表，进行一个范围的查找，显然是不太方便的， If you want to search a range of hash table, it apparently is not very convenient,
还有一种情况，对于重复关键码， And for duplicate key,
其实，我们散列也是不支持的， Hash doesn’t support it in fact.
如果真的允许它重复，我在散列之后，要建立其他的一个就是重复关键码的这么一个链表， If I allow it to repeat, I need to build another duplicate key chain table after the hash,
就是一些辅助技术来实现， That is some auxiliary technology to realize.
在这一章的内容里面，我们的散列不考虑这样的一个范围检索，也不考虑重复关键码的情况 In this chapter, the hash retrieval do not consider such a range, and repeat key.
还有一种情况，就是散列的这个方法也不适合基于磁盘的应用， There is a kind of situation; a hash of this method is not suitable for applications based on disk,
当然，也有一些说有散列文件等等，其实目前基于磁盘的散列，用的不是特别多， Of course, at present the hash based on the hash disk is not often used.
在基于磁盘的一个检索和索引技术里面，我们主要是基于B树和B+树来进行的， In a searching and indexing technology based on the disk, we are mainly based on the B and B + tree,
我们来定义一个非常重要的概念，也就是平均检索长度 Then we define a very important concept, the average length of retrieval.
平均检索长度关心的就是对于这样一个数据集， The average search length concerns, for such a data set,
平均情况下，我大概需要比较这个数据集里面，有多少个元素，我才能够找到，我相应的记录， In the average case, I probably need to compare how many elements in the data set, I am able to find the related record.
这样的话，平均检索长度跟检索每一个关键码的概率相关， Then the average length of retrieval is related to the probability of each key.
而且跟检索关键码所需要的记录比较的次数相关， And related to the number of comparisons needed for indexing the key.
平均检索长度是衡量检索算法的一个优劣的重要标准， The average search length is the important measure of measuring the retrieval algorithm.
我们可以定义为ASL=∑Pi*Ci Then we can define it as ASL=∑Pi*Ci.
Pi是整个这个数据集里面第i个元素的概率， Pi is the the probability of the ith element inside the data set,
Ci是在找第i个元素的过程中，我可能还比了其他的这个记录， For Ci, in the process of for the ith element, I may also compare the other the record,
看看，啊，我通过几次比较，才能够找到相应的这第i个元素， To see how many times I need to find the ith element.
也就是说，比较的次数 That is the number of comparison.
我们整个这个数据集里面所有的元素， For all elements in our data set,
它们的检索的频率和相应的被检到这个长度，我们给他一个求和， We sum up the frequency of indexing and the related length,
就得出我们的整体的平均检索长度， To arrive at the average index length.
评估检索算法，还有其他的几个因素也需要考虑 To assess the retrieval algorithm, other factors also need to consider.
例如如果你要设计这么一个检索算法，你可能还要用到一些，什么样的存储的，空间量， For example, if you want to design such a retrieval algorithm, you may have to use what kind of storage, and space,
另外就是，我写这个算法，是不是非常的繁杂， Another is whether this algorithm I write is very multifarious,
如果是非常的难以实现，而且难以维护，也不是一个好的算法， If it is very difficult to achieve, and difficult to maintain, it is not a good algorithm,
再给大家留一下思考题 Now leave your questions for you.
例如对这么一个线性表，只有abc这三个元素， For example, for such a linear table which only has ABC three elements,
我们检这个a、b、c的概率分布是0.4,0.1,0.5， the probability distribution of retrieving a, b, c is 0.4, 0.1, 0.5.
我们算一下，它的平均检索长度是多少， how much is the average length of retrieval,
这个时候，我们只算这个成功的检索， This time, we only calculate the successful retrieval,
也就是说，我只检a，b，c，我也不检其他的，这样的一个检索的ASL平均检索长度 That is to say, I just retrieve a, b, c, not others, the average search length，ASL.
谢谢大家。 Thanks a lot.