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

What is an index?

If there is no index, the number of scanned records is greater than the number of indexed records

The index stores the value of the index column (for example, if id is the index column, then the value of the index column), and the in-memory address of the row corresponding to the index value (or store the data of the row directly)

SELECT * FROM user WHERE username= 'jiajun', username builds the index. If the data structure of the index is a hash table, then the O (1) complexity can find the location of the record by calculating the hash value of jiajun.

Hash index

Under equivalent search, there is no hash conflict at this time. In this case, the efficiency is very high.

But in the scope search, because the hash is not orderly, then the scope search, the advantages of the hash table can not be brought into play.

In the case of hash conflicts, the search efficiency will decrease.

Disk read

Disk reading steps: fixed cylinder, fixed track, fixed magnetic block

Disk time is mainly spent on positioning cylinder, so if you want to improve the speed, in the case of the same amount of data, put as much data on the disk block as possible, then this can reduce the number of times of head positioning cylinder movement and reduce the number of IO.

Binary search tree

The value of all nodes in the left subtree is less than the value of its root node.

The value of all nodes in the right subtree is greater than that of its root node.

The left and right subtrees of any node are binary search trees.

There are no nodes with equal key values.

Analysis.

The search complexity of binary search tree is up to lgn.

But is there any way to reduce the number of IO, that is, to reduce the height of the tree?

B-tree

(M-order tree m-bank 2

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.