Bug #77342 Documentation references InnoDB, MyISAM and MEMORY as having b-tree indexes
Submitted: 13 Jun 2015 2:27 Modified: 19 Jun 2015 14:17
Reporter: Justin Swanhart Email Updates:
Status: Closed Impact on me:
Category:MySQL Server: Documentation Severity:S3 (Non-critical)
Version:all OS:Any
Assigned to: CPU Architecture:Any
Tags: indexes

[13 Jun 2015 2:27] Justin Swanhart
MySQL documentation claims in many places that InnoDB uses B-Tree indexes.  I asked Jeremy Cole about this, as he documents the very detailed technical description of InnoDB's B+Tree indexes online.  Since the technical description on his pages matches that of the high leveldescription a b+tree in Wikipedia, and since we know that the description is known to be good, as tools are based on it, then that means that InnoDB must use a B+Tree.

Please update the documentation to reflect that InnoDB uses B+Tree, not B-Tree indexes.  If the other storage engines also use B+Tree indexes, then all instances of b-tree should be replaced with b+tree.

Here is a very good example.  A whole page that talks about b-tree indexes: Compression of B-Tree Pages

Also the storage engine feature matrix for each storage engine says b-tree.  

How to repeat:
read stuff

Suggested fix:
change stuff
[13 Jun 2015 5:25] Umesh Shastry
Hello Justin,

Thank you for the report.

[15 Jun 2015 14:40] Stefan Hinz
Hi Justin,

Which part of the documentation were you reading? Can you provide a URL

[17 Jun 2015 7:47] Stefan Hinz
Posted by developer:
Dan: Please try this Google search to find instances of B-tree in the docs:
site:dev.mysql.com InnoDB indexes are B-trees
Verify with the devs that this should really be B+-tree instead of B-tree.
If they verify, please change the docs accordingly.
[17 Jun 2015 8:48] Stefan Hinz
Justin: Please ignore my request for more info. We're working on this already.
[19 Jun 2015 14:17] Daniel Price
The use of the term "B-tree" is intended as a reference to the general class
of index design. For advanced users seeking more information, we have updated
the B-tree term in the MySQL glossary to include the following information:


"The use of the term B-tree is intended as a reference to the general
class of index design. B-tree structures used by MySQL storage engines may
be regarded as variants due to sophistications not present in a classic
B-tree design. For related information, refer to the InnoDB Page Structure
Fil Header section of the MySQL Internals Manual."


We have also added more links in the reference manual to the B-tree glossary

The revised content should appear on-line within 24 hours.

Thank you for the bug report.