I did some search on the matter and I found out that Mysql uses B+Tree index, but when I run "show index" the index type that I get is Btree. And I found in this article that Mysql uses both Btree and B+tree. If it is true that it uses both; why is it named Btree without mentioning B+tree, in which case each one is used. I know the difference between the two, and I want to do some queries to figure out the difference in performance between B-tree and B+tree indexes. Which leads to my second question, is there a big difference between the two in performing certain queries, if yes, please give an example. Thank you in advance.
6
-
Looks like a B+ Tree - see here. The different appears to be that in a B Tree, the last leaf node in a branch doesn't point to the next node by order in the tree - i.e. it doesn't point across the end of the leaves - in a B+ Tree, it does!– VéraceCommented Apr 20, 2018 at 19:47
-
@Vérace I have seen that link before when I was reading about the matter, and it is so confusing to me. The explanation and figure is actually that of B+tree, but ,like mysql, the writer is calling it B-tree. I don't know if it was intentional or if he just made a mistake. I am started to think that it doesn't matter if it is B-tree or B+tree, if people are referring to them by the same name, the difference between them must be of no importance.– Noussa SmileyCommented Apr 20, 2018 at 22:32
-
1I think it does matter. B Trees and B+ Trees are not the same thing! A B Tree is simpler than a B+ Tree - with a B Tree, there are no pointers to the next element and the tree has to be traveresed - with a B+ Tree, that process is made a lot easier!– VéraceCommented Apr 20, 2018 at 22:36
-
@Vérace so was it by mistake that he called B-tree in the link you gave?– Noussa SmileyCommented Apr 20, 2018 at 22:43
-
I think so. The terminology seems to be a bit ambiguous - no surprise when it comes to MySQL! :-)– VéraceCommented Apr 20, 2018 at 22:50
|
Show 1 more comment
2 Answers
InnoDB uses B+Tree indexes, not B-Tree. All details about InnoDB data structures can be found here. You may also want to look at these diagrams. The author of both the resources, Jeremy Cole, was head of MySQL team at Google.
Why is the syntax BTREE instead of B+TREE? This question should be posed to some MySQL or MariaDB engineer, but I see at least two possible reasons:
- B+TREE would be a very bad keyword, because it contains
+, which is usually an operator. - That syntax is older than InnoDB. It is probably as old as the
ISAMstorage engine, which exists no more. It is very possible that B-TREE was used at that time.
Why does the documentation state that InnoDB uses B-Tree? Well, not all MySQL users are supposed to know what B+Tree is. This may be an oversimplification, but in that context it seems to me acceptable.
You wrote that you know the difference between B-Tree and B+Tree. Than the different performance characteristics should be clear:
- B+Tree is faster for sorting;
- B-Tree is faster when you insert values in the middle.
But in general, B+Tree is considered superior. How much? I don't know, but surely not orders of magnitude.
answered Apr 20, 2018 at 21:10
-
thank you for the explanation, but you didn't comment on what they said in the article(that Mysql uses both ) are they perhaps talking about other engines that might be using B-tree, do you know any that use B-trees. I really need to make a B-tree index and another B+tree to see the difference in speed between the two. Commented Apr 20, 2018 at 22:21
-
thank you for your answer, but you didn't comment on the link I gave, it said that Mysql uses both B-tree and B+tree, so does it mean that there are other engines that use B-tree, cause so far the one I looked up use B+tree, unless I got things wrong. And what I meant by difference between the two is; if there are queries that are executed faster when the Commented Apr 20, 2018 at 22:39
-
It is possible that MyISAM uses B-Trees, but it would be weird. Other engines don't, imo. But I think I answered about the difference: ORDER BY and GROUP BY take advantage of B+Tree. Commented Apr 26, 2018 at 21:01
-
I believe that the article is simply wrong. For sure it is wrong when it says that MEMORY uses both HASH and BTREE: it only supports HASH. Commented Apr 26, 2018 at 21:03
-
1@FedericoRazzoli - I'm pretty sure
MEMORYused to have onlyHASHindexes;BTree(B+Tree??) was added later. Commented May 7, 2018 at 18:14
A B+Tree is a just a binary search tree, like a B-Tree, where,
- The leaves (buckets) have links to the right and left siblings buckets), making the tree an index into a linked list. Usually each bucket is sized to be one disk read.
- Data is only stored in the leaf.
A B-Tree for reference stores data in the nodes, and leaves, and has no such link because scanning requires backtracking.
The idea of a B+Tree is to maximize read-size for disk seeks. It's unlikely that any database that implements a B+Tree would use B-Tree, unless they're only ever interested in Index Seeks, and not Index Scans. The overhead of the link isn't substantial. Not to mention, in the method of B+ tree gives rise to any model of concurrency, see the Lehman and Yao.
It's important that all of these differences are mere optimizations on the same idea. For instance, that Lehman and Yao paper above references B- Trees in the abstract and then mistakenly (imho), says "we consider a simple variant of the B-tree (actually of the B*-tree, proposed by Wedekind)". That's weird, because I think Wedekind proposed a B+Tree.
These terms are grossly confusing. Check out this "The Ubiquitous B-Tree" published in 1979 if you really want a waste a day,
Perhaps the most misused term term in the B-Tree literature is the B*-Tree.
answered Apr 20, 2018 at 20:20
