Mysql InnoDB storage structure (B+Tree)

Disadvantages of binary tree: the amount of data is easy to form a long linked list.

Disadvantages of red-black tree (essentially balanced binary tree) : although rotation is used to change the length of unilateral side, but when the data is large, the tree height is too high to query.

Hash Hash algorithm that does not support range query

Disadvantages of b-tree: Although the height of each node is 3, each node contains index column values and row data, resulting in a small storage capacity. The absence of Pointers between leaf nodes causes range lookups to have to be looked up from the root node each time

Disadvantages of B+Tree(variant of b-tree) : if a row of data is 1kb, the maximum number of indexes is 20 million. (Each node is 16KB in size. Leaf nodes store full data. Non-leaf nodes redundancy index column values and store the position of leaf nodes (6B). A bigint is 8B, a node is about 1170, because there are two layers so 1170117016=21902400

Index and leaf are both incremented from left to right, and are bidirectional Pointers used between leaf nodes. Can have good support for range lookups.

Clustered index non-clustered index Clustered index innoDB:

If the primary key is not actively set, the first unique index column that does not contain NULL is selected as the primary key column and used as a clustered index. If there is no such index, a clustered index is generated using the row number as the primary key. This row number is 6bytes, incremented. You can use select _rowid from table. There are two files: index file and table structure file

Non-clustered index (MYISAM):

The index file and the data file are stored separately (the leaf node index column of the index file corresponds to the address of the data in the data file). There are three files: an index file, a data file, and a table structure file

Innodb tables must have primary keys which is a B+Tree feature.

Index types can also have hash structures in addition to BTREE(actually B+Tree). Hash is not suitable for range lookup. Each leaf node points to another leaf node