B tree/B+ Tree
This article elaborates the principle of multi-way search tree, suitable for beginners to read, as well as veteran review. The full text is 2000 words and the reading time is 10 minutes.
If you have used MySQL, you must be familiar with the B+ tree, the MySQL index structure is B+ tree. The idea of a B+ tree is that it’s above a B tree, and what is a B tree?
In computer science, a B-tree is a self-balancing tree that keeps data in order. This data structure allows data lookup, sequential access, insertion, and deletion to occur in logarithmic time. A B tree, generally a generalized binary search tree, can have more than two child nodes. Different from the self-balanced binary search tree, the B tree optimizes the read and write operations of large chunks of system data. B trees reduce the intermediate process of locating records and thus speed up access. A B-tree is a data structure that can be used to describe external storage. This data structure is often used in database and file system implementations. — Baidu Encyclopedia
Note: B- trees are equivalent to B trees, not B minus trees
B tree and B plus tree
The main differences between B trees and B+ trees are:
- B tree data (or Pointers to data) exists in each node, whereas B+ tree data (or Pointers to data) exists only in leaf nodes, and non-leaf nodes only have indexes.
- B tree lookups may stop at any node
- Non-leaf nodes of a B+ tree can store more index values with higher order
- The leaf nodes of B+ tree are linked by bidirectional linked list to improve the efficiency of sequential query
- B+ trees are better at interval lookup than B trees
A B tree is more like a multipath lookup tree, where each node contains not only an index but also specific data (or Pointers to data)
MySQL indexes, whether MyISAM or InnoDB, are all B+ trees at the bottom. The difference between MyISAM and InnoDB lies in the following: MyISAM’s primary key index and secondary index, leaf nodes are Pointers to data values, and data values are stored separately. InnoDB’s primary key index leaf node stores data values instead of Pointers. Secondary index leaf node stores data values in addition to indexes. (Read more at the end.)
We all know that MySQL uses the B+ tree structure, but where does the B tree structure apply?
Answer: MongoDB.
As we all know, MongoDB is a NoSQL database. For NoSQL databases, the read and write efficiency of single key is higher than that of interval query.
Since the data of B+ tree are all on the leaf node, the query time complexity is relatively stable at O(logN), while the query of B tree can be completed at O(1) at the earliest. At the same time, the data of B tree exists on any node, so it is convenient to read the data.
In the index Structure of non-relational databases, there is another tree Structure that we rarely talk about — Log Structure Merge (LSM), which is the main design idea in HBase. In the next article, we will talk about LSM in detail.
Exists only in leaf nodes, non-leaf nodes only have indexes
Note: The following is an introduction to MyISAM and InnoDB implementations, excerpted from the web for interested readers
MyISAM index implementation
1. Primary key index
MyISAM engine uses B+ tree as index result, the data field of leaf node stores the address of data record. The following figure shows the primary index of MyISAM table, Col1 primary key.
2. Secondary indexes
** In MyISAM, there is no structural difference between primary and secondary indexes, except that primary indexes require a unique key, while secondary indexes can duplicate keys. ** Create a secondary index on Col2 below
Also a B+Tree, data field holds the address of the data record. Therefore, the index retrieval algorithm in MyISAM is to search the index according to THE B+Tree search algorithm. If the specified Key exists, the value of its data field is extracted, and then the corresponding data record is read with the value of the data field as the address.
MyISAM’s index is also called “non-clustered” to distinguish it from InnoDB’s clustered index.
InnoDB index implementation
1 Primary key index
The same B+ tree is implemented in a completely different way. The InnoDB table data file itself is an index structure. The data field of the leaf node of the tree holds complete data records. This kind of index is called clustered index.
Since InnoDB’s data files themselves are aggregated by primary keys, InnoDB requires tables to have primary keys (MyISAM can’t). If not explicitly specified, mysql automatically selects a column that uniquely identifies the data record as the primary key. If no such column exists, mysql automatically generates an implied field for the InnoDB table as the primary key. This field is 6 bytes long and of type long integer.
2 Secondary Index
All secondary indexes in InnoDB refer to the primary key as the data field. The following figure shows a secondary index defined on Col3
So InnoDB indexes provide very fast primary key lookup performance. However, its secondary index will also contain primary key columns, so if the primary key definition is large, the other indexes will also be large. InnoDB does not compress indexes.
Clustered index implementations make searching by primary key very efficient, but secondary index searches require retrieving the index twice: first, retrieving the secondary index for the primary key, and then using the primary key to retrieve records from the primary index.
The way indexes are implemented by different storage engines is very helpful for proper use and optimization of indexes. For example, with InnoDB’s index implementation, it is easy to see why it is not recommended to use fields that are too long as primary keys because all secondary indexes reference the primary index, and a long primary index can make the secondary index too large. For example, using non-monotonic fields as primary keys is not a good idea in InnoDB, because InnoDB data files themselves are a B+Tree. Non-monotonic primary keys cause data files to be constantly split and adjusted to maintain B+Tree features when new records are inserted, which is inefficient. Using an increment field as a primary key is a good choice.
Extract some source: www.cnblogs.com/balfish/p/8…