The index

  • Indexing is to improve query efficiency for faster retrieval
  • Index data structure analysis

hash

Red and black tree

B tree

B + tree

hash

  • Key value types are suitable for equivalent search, but not range search. Hash is memory based and has a large amount of database data

Red and black tree

  • You have to maintain the balance of the tree, the height of the tree is uncontrollable. The number of I/OS required is not controllable, and the time complexity is O(logN).

B tree

  • The data is stored on the leaf node (Page), although the height is reduced, but the query performance is still a bottleneck, because Myqsl stores 16KB per Page, if a data with 1Kb, a Page can only store 16 data. You can only have 16 byte points.
  • Range lookups are not supported

B + tree

  • Index nodes are separated from data nodes. A B+ tree of 3 height can store 20 million data. 16Kb/(8B + 6B) =1170, 1170x1170x16(number of data nodes) equals about 20 million data
  • The leaf node of B+ tree is a bidirectional linked list that supports range query. The height of the tree is usually (1-3) and the IO times need to be stable

B+ tree in Mysql

  • The page consists of the following

File Header Describes the general status information of the current page

Page Header describes the page-specific state information

InfNum supreNum indicates the minimum Infimum record and the maximum Supremum record

User Record Stores Record data inserted by users, that is, User records

Free Space Remaining Space

Page Directory A Page Directory contains several slots, each of which stores the address offset of a particular data record on the Page

The unclustered index data region stores the primary key