Shulou(Shulou.com)06/01 Report--

This article mainly introduces "what is Java linear index search". In daily operation, I believe many people have doubts about what Java linear index search is. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubt of "what is Java linear index search?" Next, please follow the editor to study!

Linear index lookup

Index: the process of associating a keyword with its corresponding record. An index consists of several index entries, each of which should at least contain information such as the location of the keyword and its corresponding record in memory.

According to the structure, indexes can be divided into linear index, tree index and multi-level index.

A linear index organizes a collection of index items into a linear structure, also known as an index table. Including dense index, block index, inverted index.

1. Dense index:

A perfect introduction: map each record in the dataset to an index entry

My mother is old and has a bad memory, so she often can't find anything at home, so she came up with an idea. She used a small book to record the location of all the small things in the family, such as the hukou book in the drawer under the right-hand nightstand, the needle and thread in the drawer in the middle of the TV cabinet, and the banknote in the wardrobe. In short, her old man recorded the location of these small items in a small book, and every once in a while sorted out the belongings in her home, and put them back in the same place after using them, so that she could hardly find anything again. From this incident, we can see that although the items in the home are disordered, it is very easy to find if there is a small book record, and this small book is the index.

Dense index refers to the online table, each record in the dataset corresponds to an index entry.

For the index table of a dense index, the index items must be arranged in order by key. Through the search of the index entry, you can find the address of the lost result, but if the dataset is very large, say hundreds of millions of dollars, it means that the index has the same data size, which may require repeated queries on memory and hard disk, and performance may be degraded.

two。 Block index

Introduction: how to collect books in the library

Block ordering needs to meet two conditions: intra-block disorder (better order, higher cost) and inter-block order.

For a chunked ordered dataset, each block corresponds to an index item. this indexing method is called block indexing.

The maximum key code, block length, and block header pointer are easy to understand.

Average lookup length ASL is the average lookup length in the index table + the average lookup length in the record (dataset).

Suppose there are m blocks, and there are t records in each block, obviously n = m * t.

So ASL = (msq1) / 2 + (twee1) / 2 = (NPABG + t) / 2 + 1. The minimum value of the above formula, that is, n _ n = t _ ^ _ 2, then the smallest ASL = n ^ (1max ~ 2) + 1.

It can be seen that the efficiency of block index is much higher than that of sequential search o (n), but the specific half search method O (logN) is still different. generally speaking, block index greatly increases the speed of overall search without the need for ordering of subdivided blocks, so it is widely used in the application of database search and other technologies.

3. Inverted index

Introduction: how the search engine searches, it can display the best matching content of the search at a very fast speed.

The structure of the index item is a secondary key code and a record number table, where the record number table stores the record number of all records with the same keyword (which can be a pointer to a record or the primary key of that record). Such an indexing method is inverted indexing.

At this point, we type book and the search will immediately show 12 articles.

The general structure of index items is:

1. Secondary keys, such as the English words above.

two。 Record number table, such as the article number above

Inverted index comes from the need to find records according to the values of attributes (or fields, secondary keys) in practical applications. Each item in such an index table includes an attribute value and the address of each record with that attribute value. Because the attribute value is not determined by the record, but the location of the record is determined by the attribute, it is called an inverted index.

The advantage of inverted index is obviously that finding records is very fast, which is basically equivalent to finding records without reading records after generating index tables, that is, you can get results. But its disadvantage is that the record number is variable in length, more or less.

Ps. In reality, search technology is much more complex and involves too much content.

At this point, the study of "what is Java linear index lookup" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.