要了解B树索引是如何形成的，让我们想象一个没有它们的世界，并尝试解决一个典型的问题。在此过程中，我们将讨论我们将面临的问题以及解决这些问题的方法。
介绍
在数据库世界中，有两种最常见的信息存储方式：
- 基于基于日志的结构。
- 基于页面。
第一种方法的优点是它使您可以轻松，快速地读取和保存数据。新信息只能写入文件的末尾（顺序记录），这可以确保较高的记录速度。Leveldb，Rocksdb，Cassandra等基础使用此方法。
第二种方法（基于页面）将数据分成固定大小的块并将其保存到磁盘。这些部分称为“页面”或“块”。它们包含表中的记录（行，元组）。
MySQL，PostgreSQL，Oracle等使用这种数据存储方法。并且由于我们正在谈论MySQL中的索引，因此我们将考虑这种方法。
MySQL中的数据存储
因此，MySQL中的所有数据都作为页面保存到磁盘。页面大小由数据库设置控制，默认情况下为16 KB。
每页包含38个字节的标题和8个字节的结尾（如图所示）。而且分配给数据存储的空间没有完全填满，因为MySQL在每个页面上都留有空白空间以供将来更改。
在进一步的计算中，假设页面的所有16 KB都填充了我们的数据，我们将忽略服务信息。我们不会深入研究InnoDB页面的组织，这是另一篇文章的主题。您可以在此处了解更多信息。
例如，由于我们在上面同意不存在索引，因此，我们将创建一个不包含任何索引的简单表（实际上，MySQL仍会创建一个索引，但在计算中不会考虑到它）：
CREATE TABLE `product` (
`id` INT NOT NULL AUTO_INCREMENT,
`name` CHAR(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
`category_id` INT NOT NULL,
`price` INT NOT NULL,
) ENGINE=InnoDB;
并执行以下请求：
SELECT * FROM product WHERE price = 1950;MySQL将打开存储表中数据的文件，
product并开始遍历所有记录（行）以搜索所需的记录，并将price找到的每一行的字段与查询中的值进行比较。为了清楚起见，我特别考虑对文件进行全面扫描的选项，因此MySQL不适合从缓存中接收数据的情况。
我们可以面对什么问题？
硬碟
由于我们将所有内容存储在硬盘驱动器上，因此让我们看一下它的设备。硬盘在扇区（块）中读写数据。该扇区的大小可以从512字节到8 KB（取决于磁盘）。几个连续的扇区可以合并为群集。
可以在格式化/分区磁盘时设置群集大小，即以编程方式完成。假设磁盘上的扇区大小为4 KB，并且使用16 KB的群集大小对文件系统进行分区：一个群集由四个扇区组成。我们记得，MySQL默认情况下以16 KB页面的形式将数据存储在磁盘上，因此一页可以容纳一个磁盘集群。
假设存储了500,000件商品，让我们计算一下产品板将占用多少空间。我们有三个四字节字段
id，price和category_id。我们同意所有记录的名称字段都填充到末尾（所有100个字符），每个字符占用3个字节。 （3 * 4）+（100 * 3）= 312个字节-这是表的一行占多少，再乘以500,000行，得出表的权重为product156兆字节。
因此，要存储此标签，硬盘上需要9750个群集（9750页，16 KB）。
当保存到磁盘时，将使用空闲簇，这导致一个板（文件）的簇在整个磁盘上“散布”（这称为碎片）。随机读取位于磁盘上的此类内存块称为随机读取。由于必须多次移动硬盘磁头，因此读取速度较慢。要读取整个文件，我们必须跳过整个磁盘以获取所需的群集。
让我们回到我们的SQL查询。要查找所有行，服务器将必须读取分散在磁盘上的所有9750个群集，并且移动磁盘读取头将花费大量时间。我们使用数据的聚类越多，搜索速度就越慢。此外，我们的操作将阻塞操作系统的I / O系统。
最后，读取速度很慢。“挂起”操作系统，阻塞了I / O系统；并进行大量比较，检查每一行的查询条件。
我自己的自行车
我们如何独自解决这个问题？
我们需要弄清楚如何改善表查找
product。让我们创建另一个表，在该表中，我们仅将字段price和指向记录（磁盘上的区域）的链接存储在表中product。让我们直接接受一个规则，即在将数据添加到新表时，我们将以排序形式存储价格。
它给我们什么？与主表一样，新表也逐页（以块为单位）存储在磁盘上。它包含价格和主表的链接。让我们计算一下该表将占用多少空间。价格占用4个字节，并且对主表（地址）的引用也为4个字节。对于500,000行，我们的新表仅重4 MB。这样，新表中的更多行将适合一个数据页，并且需要更少的页面来存储我们的所有价格。
如果一个完整的表需要9,750个硬盘群集（或者在最坏的情况下，需要9,750个硬盘跃点），则新表仅适合250个群集。因此，磁盘上已使用集群的数量将大大减少，因此将花费在随机读取上的时间。即使我们阅读了整个新表并比较了值以找到合适的价格，在最坏的情况下，新表的簇也要跳250次。找到所需的地址后，我们将读取另一个包含完整数据的群集。结果：251个读数与原始9750个读数相比。差异非常明显。
另外，要搜索这样的表，您可以使用例如二进制搜索算法（因为列表已排序）。这将节省更多的读取和比较操作次数。
让我们将第二张表称为索引。
万岁！我们提出了自己的
但是请停止：随着表的增长，索引也将越来越大，最终我们将回到最初的问题。搜索将再次花费很长时间。
另一个指标
如果要在现有索引之上创建另一个索引？
仅这次，我们不会记下该字段的每个值
price，而是将一个值与索引中的整个页面（块）相关联。也就是说，将出现一个附加级别的索引，该索引将指向前一个索引（存储第一个索引的数据的磁盘页面）上的数据集。
这将进一步减少读数的数量。索引的一行占用8个字节，也就是说，我们可以在一个16 KB的页面上容纳2000条这样的行。新索引将包含指向第一个索引的2000行数据块的链接以及该数据块的起始价格。一条这样的行也占用8个字节，但是数目却急剧减少：从500,000个减少到250个。它们甚至可以放入一个硬盘群集中。因此，为了找到所需的价格，我们将能够准确确定它在2000行的哪个块中。在最坏的情况下，要找到相同的记录，我们：
- 让我们从新索引中读取一个。
- 经过250行之后，我们从第二个索引找到了到数据块的链接。
- 考虑一个群集，其中包含2000行，这些行包含价格和指向主表的链接。
- 检查了这2000行之后，我们将在磁盘上找到所需的一个和另一个时间跳转，以读取最后一个数据块。
我们将总共获得3个集群跳跃。
但是这个级别迟早也会填充很多数据。因此，我们将不得不重复所做的一切，一遍又一遍地添加新的层次。也就是说，我们需要一种用于存储索引的数据结构，该结构将随着索引大小的增加而增加新的级别，并独立地平衡它们之间的数据。
如果将表翻转过来，以使最后一个索引位于顶部，而主表与数据位于下方，则我们将得到与树非常相似的结构。
B树数据结构的工作原理相似，因此选择它们是出于这些目的。
B树简介
MySQL中最常用的索引是B树（平衡搜索树）排序的索引。
B树的一般想法类似于我们的索引表。值按顺序存储，树的所有叶子到根的距离都相同。
就像我们的带有索引的表存储了一个价格值以及指向包含该价格范围内的一系列值的数据块的链接一样，B树根也存储了一个价格值以及一个指向磁盘上存储区域的链接。
首先，读取包含B树根的页面。此外，在输入键的范围之后，有一个指向所需子节点的指针。读取子节点的页面，从键值获取指向数据表的链接，并从该链接读取包含数据的页面。
InnoDB中的B树
更具体地说，InnoDB使用B +树数据结构。
每次创建表时，都会自动创建B +树，因为MySQL会为主键和辅助键存储这样的索引。
辅助键还存储主键（集群）的值作为对数据行的引用。因此，辅助键会随着主键值的大小而增长。
另外，B +树使用子节点之间的其他链接，从而提高了在一系列值上的搜索速度。在此处阅读有关InnoDB中b +树索引的结构的更多信息。
加起来
b树索引通过显着减少从磁盘读取的信息量，当在一系列值范围内搜索数据时提供了很大的优势。它不仅在按条件搜索期间参与，而且在排序，联接和分组期间也参与。在此处阅读MySQL如何使用索引。
对数据库的大多数查询只是用于按值或按值范围查找信息的查询。因此，在MySQL中，最常用的索引是b树索引。
同样，b树索引在检索数据时也有帮助。由于主键（聚集索引）和建立非聚集索引的列的值（第二键）存储在索引叶中，因此您无法再访问该数据的主表并从索引中获取它。这称为覆盖指数。您可以在本文中找到有关聚簇索引和非聚簇索引的更多信息。
索引（如表）也存储在磁盘上并占用空间。每次向表中添加信息时，索引必须保持最新状态，以监视节点之间所有链接的正确性。这会产生写信息的开销，这是b树索引的主要缺点。我们牺牲写入速度来提高读取速度。
- MySQL . 3-
: ,
: 2018 - blog.jcole.us/innodb
- dev.mysql.com/doc/refman/8.0/en/innodb-storage-engine.html