This is the 8th day of my participation in the More text Challenge. For details, see more text Challenge

Recently, when I was reading some books on mysql, a year flashed through my mind, B+ tree here I know, B tree I also roughly understand, that he two is what, oh ha ha ha, forgot, so sometimes it is necessary to summarize a wave

Before writing a tree, consider a question: in the development process, we are most commonly used to find data, is hashmap, a commonplace, then have you ever thought why to choose a tree instead of hash algorithm? And the Memory engine now supports hashing! Save questions for last…

B tree

B-tree is b-tree, ==> b-tree = B-tree, because of translation problems, it will make beginners misunderstanding, remember, B-tree is B-tree.

Too many concept here is not to say, a lot of online, within the scope of cognitive main said some I personally think that need to be aware of a key, B tree is also known as multipath balance search trees, is different from the child nodes of the binary tree is that it is not two, but multiple, and believe that everyone know the concept of page, he is we are the basic units of data storage,

This is what I looking for a figure from baidu, actually this picture can’t express my meaning, because it write on each node of data, B each node of the tree to store data, so the amount of data that can be stored per page is less, it is necessary to compare, and we are looking for data to find below nodes up if you don’t have to return to the root node continue to scroll down, So repeatedly until the search, and every time to run back and forth root node need to keep IO, and page data is small, also need to keep IO page data, most of the time is used in the run, the real search time is not much;

B + tree

The disadvantage of B tree, and then B + tree is about to optimize these shortcomings, of course, first of all, in the case of too little page data storage nodes, put all the data in the leaves, and all intermediate nodes storing index value, which could maximize storage of keywords, for the need to constantly find node, a didn’t look up to the need to return to the root node to continue down the traversal, A B+ tree allows each leaf node to have Pointers to neighboring leaves, and the leaves themselves are linked in order from the smallest to the largest keyword

Baidu on the figure is very interesting, very good expressed my ideas each layer with two-way chain table joins each page, whether it is in the page directory tree B or B + tree is a dichotomy, because their data are order, so don’t worry about why use dichotomy, there is someone thinking, that I don’t have to the primary key index to do, And I built a secondary indexes, here, if you have your own created index, it will according to your new indexes to regenerate into a small tree, the next, there is a small tree can check here, so, this is what other people say index is not the more the better, and modify the data need to maintain the tree is much, also, remember, pay attention to prevent back table query yo,,,

Answer the questions

Finally, to answer the question, you can’t use a range query for a Hash index, because the Hash values match exactly, and you can’t avoid a full table scan, and on top of that, you have Hash collisions, which you should know if you’ve studied HashMap, and the tree structure is a perfect way to avoid these problems