BTREE, B + tree and hash index

  hash Index is characterized by high retrieval efficiency , Search once to locate ,BTree You need to look down from the root node , After many times IO Visit to find the results , therefore hash Indexing is much more efficient than BTree.
but hash It also has many limitations and defects ：
1.hash The target can only be accurately located by index , Instead of range query .
2. because hash Only the past is saved hash After calculation hash Value and corresponding line pointer , So it can't be used for sorting .
3.hash If the index encounters a large number of hash Equal values , Then a large amount of record pointer information will be stored in the same hash Value up , In this way, it will be troublesome to locate a record , The final efficiency is not necessarily better than BTree High index .
4. For composite indexes ,hash The index will combine the combined indexes and then calculate hash value , Instead of calculating separately hash value , So by combining the first several index key values of the index ,hash The index cannot be used .
5. Because different index keys may have the same hash value , therefore hash The index cannot avoid full table scanning at any time .

BTree Also called balanced multiple search tree . A tree m Step B Trees (m Fork tree ) Its characteristics are as follows ：
1. Each node in the tree contains at most m A child （m>=2）;
2. Except for root and leaf nodes , Every other node has at least [ceil(m / 2)] A child （ among ceil(x) It's a function with an upper bound ）;
3. If the root node is not a leaf node , At least 2 A child （ A special case ： No child's roots , That is, the root node is the leaf node , The whole tree has only one root node ）;
4. All leaf nodes appear in the same layer , Leaf node does not contain any keyword information
5. Each non terminal node contains n Keyword information （P0,P1,…Pn, k1,…kn）
6. Number of keywords n Satisfy ：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n) Keyword , And the keywords are sorted in ascending order .
8. Pi(i=1,…n) Is the pointer to the root node of the subtree .P(i-1) All node keywords of the pointed subtree are less than ki, But they are greater than k(i-1)

B+Tree Is in BTree An optimization based on .
1. Non leaf nodes only store key information . This can greatly increase the storage capacity of each node key Value quantity , Reduce B+Tree Height .
2. There is a chain pointer between all leaf nodes . Traversal is more convenient .
3. Data records are stored in leaf nodes .

Reference material ：
Contains a binary tree 、 Balanced binary trees 、 Balance multiple search trees （BTree）
https://blog.csdn.net/hao65103940/article/details/89032538