Database Indexes, What are they Really Made of? B+ tree is a very suitable data structure for database indexing:

(1) Very suitable for disk storage, can make full use of the principle of locality, disk preread;

(2) Very low tree height, can store a lot of data;

(3) The index itself occupies very little memory;

(4) Can well support single point query, range query, ordered query;

Database indexes are divided into Primary Inkex and Secondary Index. How InnoDB and MyISAM use B+ trees to implement these two types of indexes, and what is the difference? That’s what we’re talking about today.

MyISAM index

MyISAM’s indexes are stored separately from row records, called UnClustered indexes.

The primary key index is essentially the same as a normal index:

  • There are areas of continuous aggregationStore row records separately
  • Primary key index leaf node, stores primary key, and corresponding row recordsPointer to the
  • The leaf node of a normal index, storing index columns, and corresponding row recordsPointer to the

* Voiceover: MyISAM can have tables without primary keys. *

A primary key index and a normal index are two independent index B+ trees. When searching through the index column, the leaf node of the B+ tree is located first, and then the row record is located through the pointer.

For example, MyISAM:

t(id PK, name KEY, sex, flag);

There are four entries in the table:

1, shenjian, m, A

3, zhangsan, m, A

5, lisi, m, A

9, wangwu, f, B

Its B+ tree index structure is shown in the figure above:

  • Row records are stored separately
  • Id is PK and there is an index tree of ID with leaves pointing to row records
  • Name is the KEY, and there is an index tree of name, with leaves pointing to row records

InnoDB index

InnoDB primary key indexes are stored together with row records, so they are called Clustered indexes:

  • There is no separate area for storing row records
  • Primary key index leaf node,Stores primary keys and corresponding row records(Not Pointers)

Vo: So InnoDB PK queries are very fast.

Because of this feature, InnoDB tables must have clustered indexes:

(1) If the table defines PK, PK is the clustered index;

(2) if the table does not define PK, then the first non-empty unique column is the clustered index;

Otherwise, InnoDB creates a hidden row-ID as the clustered index;

There can only be one clustered index, because rows can have only one clustered store on the physical disk.

InnoDB can have multiple normal indexes, which are different from clustered indexes:

  • A leaf node of a normal index,Store the primary key(Not a pointer either)

The implications for InnoDB tables are as follows:

(1) It is not recommended to use a long primary key, such as char(64), because all normal indexes store primary keys, which would make the normal index too large;

(2) It is recommended to use the trend increasing key as the primary key, because the data row and index are integrated, so as to avoid a large number of index splitting and row record movement when inserting records;

InnoDB storage engine: InnoDB storage engine: InnoDB

t(id PK, name KEY, sex, flag);

There are still four entries in the table:

1, shenjian, m, A

3, zhangsan, m, A

5, lisi, m, A

9, wangwu, f, B

Its B+ tree index structure is shown in the figure above:

  • The id is PK, and the row record is stored with the ID index tree
  • Name is the KEY, there is an index tree of name, the leaf stores the ID

When:

Select * from t where name= ‘lisi’;

It will first locate the leaf node of B+ tree through name auxiliary index to get ID =5, and then locate the row record through clustered index.

* Voiceover: So, it actually scans the index tree twice. *

Three,

MyISAM and InnoDB both use B+ trees for indexing:

  • MyISAM index and dataseparatestorage
  • MyISAM index leafStore Pointers, primary key indexes are not much different from normal indexes
  • The InnoDBClustered indexandData rows are stored uniformly
  • InnoDB’s clustered index stores the rows themselves,Normal indexStore the primary key
  • InnoDB must have one and only one clustered index
  • InnoDB recommended useTrend increasing integer as PKAnd theIt is not advisable to use long columns for PK