MySQL Bugs: #77342: Documentation references InnoDB, MyISAM and MEMORY as having b-tree indexes

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

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

Hello Justin,

Thank you for the report.

Thanks,
Umesh

Hi Justin,

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

Stefan

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.

Justin: Please ignore my request for more info. We're working on this already.

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.