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:
None 
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
Description:
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:
3.4.2.1. 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] MySQL Verification Team
Hello Justin,

Thank you for the report.

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

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

Stefan
[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:

http://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_b_tree

"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."

https://dev.mysql.com/doc/internals/en/innodb-fil-header.html

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

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

Thank you for the bug report.