What is the index?

An index is a structure that sorts the values of one or more columns of a data table. Using an index allows quick access to specific information in a data table

My interpretation of this definition is that a data table is like a book, and an index is the table of contents in front of the book.

  • The table of contents also takes several pages – and the corresponding index requires some physical space
  • Table of contents for each section, each content module has the exact location of the page – the corresponding data in the index is the physical location of a piece of data in the table of data

With the help of this idea, I would like to record my understanding (there may be mistakes, welcome to point out).

  • When a variable is created in memory, it can be accessed at O(1) speed next time because the memory address of the variable is recorded in the computer system, so it can be reached quickly.
  • For arrays: Create an array ARR with 10 elements. Arr [5] can access data quickly with O(1) speed because: The computer system quickly reaches the memory address of ARR [0] at the speed of O(1), and then obtains the memory address of ARR [5] through other calculations such as 5-0, and then quickly arrives.
  • Create object obj with name and age attributes. Obj. Name can access data quickly with O(1) because: The memory space occupied by the object not only has the space required by the value of the attribute, but also has the value of the memory address that is bound to the attribute and records the value of the attribute. Therefore, as long as the computer system is informed of the attribute name, the value of the attribute can be quickly obtained.

Database index

Database is like a large object/array, which is nested with a layer or multi-layer object/array, the data in the database is massive, so we need to manage these data: for the database all the data set index, achieve fast access

An index is a secondary storage structure defined on the basis of a table to help quickly locate required records without checking all records. It consists of a series of index entries stored on disk, each consisting of an index field and a row pointer

The benefits of indexing?

  • By creating indexes, you can improve system performance during the query processperformance;
  • By creating a unique index, each row in a database table is guaranteed to be validuniqueness;
  • When using grouping and sorting clauses for data retrieval, it canTo reduce the queryIn theGrouping and sortingThe time.

What’s bad about indexes?

  • createIndex andmaintenanceIndexing takes time, and time goes byThe amount of dataIncrease in size;
  • The index needs to beTake up physical spaceIf clustering index is to be established, more space is needed;

What are dense and sparse indexes?

  • Dense index: there is an index entry for each record in the main file.
    • Dense index of candidate key attributes: look up the index first, then read the main file against the index;
    • Dense indexes for non-candidate key attributes:
      • The main file is sorted by index field, and the index field value in the index file is not repeated.
      • The main file index field is not sorted, but the index field value in the index file is repeated;
      • The index fields in the main file are not sorted and the index fields in the index file have no duplicate values.
  • Sparse index: there are index items corresponding to some records in the master file (the master file must be stored in order of corresponding index field attributes);

What are primary and secondary indexes?

  • Master index: There is an index item for each block. The first record of each block is called an anchor. It is usually built on the sorted fields of ordered files based on the master code, and it is a sparse index.
  • Secondary index: a secondary storage structure defined on any or more non-sorted fields of the main file. It is a dense index.

What are clustered and non-clustered indexes?

  • Clustered index: put the data storage and index together, find the index will also find the data, the main file according to the corresponding field sorted storage, index file without repeated sorted storage;
  • Non-clustered index: the data is stored in a separate index structure. The leaf nodes of the index structure point to the corresponding row of the data. The main file is not sorted according to the corresponding field.

example

Refer to the article

  • Database index – Baidu Encyclopedia
  • Database index – CSDN