磁盘存储
哇，磁盘存储这个话题听起来好高大上呀！其实就是说，我们的电脑或者手机里面的数据是如何被存储的问题。我们可以把数据理解成一摞卡片，而我们的电脑或手机就是一个卡片盒子。而我们需要做的就是把这些卡片存储到盒子里面，然后需要的时候再把卡片拿出来。
但是，问题来了，如果我们的数据很多，卡片也很多的话，我们怎么才能让电脑或手机更快地找到我们需要的数据呢？这就要用到磁盘块了。所谓磁盘块，就是指硬盘上划分出来的一块一块的空间。就好比我们的卡片盒子里面，我们可以将卡片分成一叠一叠的，每一叠就是一个磁盘块。
而我们的电脑或手机在查找数据的时候，并不是只找一张卡片，而是会一次性读取整个磁盘块的数据。这就好比我们在找一张卡片的时候，不仅把这一张卡片拿出来，还把这张卡片的前后几张卡片也拿出来看看。
而当我们的电脑或手机需要查找某个数据时，它会先找到这个数据在哪个磁盘块里面，然后才能拿到这个数据。这就好比我们在找一张卡片的时候，需要先找到这张卡片在哪一叠里面，才能找到这张卡片。
但是，电脑或手机在硬盘上存储数据的时候，并不是按照我们的卡片一样，每个数据都放进一个独立的磁盘块里面。而是将一块磁盘块分成很多个小的存储单元，然后把不同的数据分别存放在不同的存储单元里面。这就好比我们的卡片盒子里面，我们把每一叠卡片分成很多小格子，不同的卡片放在不同的小格子里面。
而就像我们在找一张卡片的时候，需要先找到这张卡片在哪一叠里面，再找到这张卡片的具体位置一样。电脑或手机在找到所在的磁盘块后也需要再找到具体的存储单元，才能获取需要的数据。
但是，如果我们的数据量很大，磁盘块的数量也会很多，这样就会导致查找数据的时间变长，效率变低。为了解决这个问题，我们可以使用树形结构来存储数据。
树形结构是一种层次化的数据结构，它可以快速定位到要找的数据。树形结构中有一个叫做根节点的节点，它是整个树的顶端，相当于我们卡片盒子的盖子。而树的每个节点下面都可以有很多子节点，就好比我们卡片盒子里面的每一叠卡片。每个节点下面还可以有很多子节点，这样就形成了一棵树。
在数据库中，我们经常使用的是B树或B+树。B树中的每个节点都有对应的key和value，而B+树则是将所有的数据记录都存放在叶子节点上。而非叶子节点上只存储key信息。这样可以大大增加每个节点存储的key数量，降低树的高度，提高了数据查找的效率。
磁盘存储这个话题虽然听起来很高深，但实际上就是把我们的数据存放在电脑或手机的硬盘上，并使用树形结构来快速定位到需要的数据。当我们在查询数据时，需要根据数据所在的位置来查找，使用B树或B+树可以让查找更加高效。
MySQL是一种关系型数据库管理系统，它通过从磁盘读取数据到内存来提高数据访问效率。MySQL以磁盘块为基本单位，在同一磁盘块中的数据会被一次性读取出来，不是按需读取。对于InnoDB存储引擎，它使用页作为数据读取单位，页是其磁盘管理的最小单位，默认大小是16kb。一行数据的大小是1kb，一个页可以存放16行这样的数据。当查找某个页里面的数据时，需要首先找到它所在的页。
在查询数据时，一个页中的每条数据都能定位数据记录的位置，这会减少磁盘I/O的次数，提高查询效率。InnoDB存储引擎在设计时将根节点常驻内存，以达到树的深度不超过3的目的，也就是说I/O不超过3次。
树形结构的数据可以让系统高效地找到数据所在的磁盘块。其中B树和B+树是两种常见的索引结构。B树的结构是每个节点中有key和value，而每一个页的存储空间是16kb，如果数据较大时将会导致一页能存储数据量的数量很小。B+Tree的结构是将所有数据记录节点按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
B+树索引具有高扇出性，因此在数据库中，B+树的高度一般都在2-4层，这也就是说查找某一键值的行记录时最多只需要2到4次I/O。聚集索引和辅助索引是B+树索引的两种类型。
一般的机械磁盘每秒至少可以做100次IO， 2～4次的IO意味着查询时间只需0.02～0.04秒。
假设每条sql信息为1kb，主键ID为bigint型，一颗高度为2，3，4高度的B+树分别可以存储多少行数据?
我们可以把 B+树的结构想象成一个大树，每个节点都分叉成多个小枝丫，而每个小枝丫的末端都是数据记录。如果我们用一个数字来表示每个数据记录，那么这个数字就是每条 sql 信息的主键 ID，而整个 B+树就是用来帮助我们快速定位这些记录的。
首先，B+树是一种树状结构，它的高度影响着它能够存储多少数据。我们假设数据记录的主键 ID 是 bigint 类型，那么它占用 8 个字节的空间。而每个节点除了存储数据记录的信息外，还需要存储指向下一个节点的指针，这个指针占用 6 个字节的空间。
然后我们来计算一下一颗高度为 2、3、4 的 B+树能够存储多少行数据。我们先假设每个数据记录的信息占用 1KB，也就是 1024 字节。
对于高度为 2 的 B+树，它的根节点指向的子节点是叶子节点，而这些叶子节点则存储着实际的数据记录。每个节点最多存储 1170 个指向下一个节点的指针，而每个节点的大小是 16KB，因此一个节点最多可以存储 1170 行数据，也就是 1170 个主键 ID。而高度为 2 的 B+树一共有两层，因此它最多可以存储的数据行数就是 1170 * 1170 = 1,368,900 行。
对于高度为 3 的 B+树，它的根节点指向的子节点是非叶子节点，而这些非叶子节点（除了叶子节点外的所有节点）存储着指向下一层子节点的指针。每个非叶子节点可以存储 1170 个指针和键值，因此一个非叶子节点最多可以指向 1170 个叶子节点。而每个叶子节点最多可以存储 1170 行数据，因此一个非叶子节点最多可以存储 1170 * 1170 行数据。高度为 3 的 B+树一共有三层，因此它最多可以存储的数据行数就是 1170 * 1170 * 1170 = 17,576,490 行。
对于高度为 4 的 B+树，同理，它的根节点指向的子节点还是非叶子节点，而每个非叶子节点最多可以指向 1170 个子节点。由于高度为 4，因此一共会有四层，而每个叶子节点最多可以存储 1170 行数据。因此，一个非叶子节点最多可以存储 1170 * 1170 * 1170 行数据。高度为 4 的 B+树最多可以存储的数据行数就是 1170 * 1170 * 1170 * 1170 = 20,348,847,000 行。也就是说，它可以存储 200亿行左右的数据。
这就是 B+树的强大之处，它可以快速地定位到数据记录，而且支持快速的插入和删除操作。因此，在数据库中，B+树被广泛地应用于索引的建立和优化。
为什么选用B+树做索引而不选用二叉树或者B树?
你是否有过这样的经历：打开电脑，想看看自己的照片或者文档，可是不知道在哪个文件夹里面？于是你开始在各个文件夹之间不停地点击，直到找到了目标文件。这个过程其实就像在磁盘里面寻找数据，而数据库索引就是帮助我们快速定位数据所在位置的工具。
在数据库中，我们需要通过一些属性值来查找数据，比如查找某个人的名字、年龄或地址等信息。如果数据量很小，我们可以通过一些简单的方法来完成查找，比如使用二叉查找树。但是如果数据量很大，这种方法就会变得非常缓慢。因为，每次查找都需要从根节点开始，一级一级地向下搜索，直到找到目标数据为止，这个过程需要不停地访问磁盘，增加了IO操作的次数，导致查询效率非常低下。
为了解决这个问题，我们发明了B树和B+树。它们经过了一些特别的设计和改进，能够更好地适应磁盘存储的特点，使得数据库索引的查询速度更快。
当我们要在数据库中进行索引查询的时候，我们需要快速地定位到所需数据所对应的位置，这个过程涉及到的数据量非常大，因此我们需要一种高效的数据结构来实现索引查询。在这种情况下，B+树成了一个非常好的选择。B+树在数据库索引中应用非常广泛，因为它有以下几个优点：
1.减少IO次数
在数据库中，索引是存储在磁盘上的。当数据量非常大时，我们不能把整个索引全部加载到内存中，只能逐一加载每一个磁盘页（对应索引树的节点）。因此，我们需要减少IO次数。而树的高度影响IO次数，B+树相对于其他树结构，如二叉树和B树，更“矮胖”，树的高度较小，可以快速定位到所需数据所在的节点，从而减少IO次数。
举个例子来说，如果我们要在整个数据库中查找一个学生的学号，如果使用二叉树，树的高度将会非常高，需要进行多次IO操作才能找到该学号对应的节点。而使用B+树，查找速度更快，只需要定位到所需数据所在节点即可，也就是说，IO操作次数更少。
2.稳定查询
在查找过程中，我们希望查询效率高且稳定，不希望有过多的波动。而B+树对于范围查找来说，仅需要遍历叶子节点链表即可，不需要排序操作，因为叶子节点已经对索引进行了排序操作。而B树则需要重复地中序遍历，找到所有的范围内的节点。因此，B+树的查询效率更高，而且更加稳定。
3.存储效率高
B+树的中间节点不保存数据，只保存索引信息，这样磁盘页能容纳更多节点元素，更“矮胖”。而B树无论是叶子节点还是非叶子节点，都会保存数据，这就导致在非叶子节点中能保存的指针数量变少，指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低。
举个例子来说，如果我们要在数据库中查找所有姓张的学生，如果使用B树，由于每个节点都保存了数据，那么在非叶子节点中要保存大量数据时，就只能增加树的高度，导致IO次数急剧增加，查询效率变低。而使用B+树，由于中间节点不保存数据，可以容纳更多节点元素，树高度较小，可以快速定位到所需数据所在节点，从而减少IO次数。
因此，虽然二叉树和B树在理论上的查找速度和比较次数最小，但是在实际的数据库索引应用中，B+树成为了最佳选择，因为它具有高效率、稳定性、存储效率高等优点。
为什么用 B+ 树做索引而不用哈希表做索引？
首先，我们需要了解一下索引的作用。索引是数据库中用于加速查询的数据结构。在进行查询时，数据库可以通过索引快速定位到需要查询的数据，避免了全表扫描的高开销。
哈希表和 B+ 树都是常用的索引结构。哈希表是将索引字段通过哈希映射成对应的哈希码，然后再存放在对应的位置。B+ 树则是一种树状结构，根据索引字段构建出一颗多层次的树，通过不断的分支和定位，最终找到对应数据所在的位置。
那么，为什么我们更倾向于使用 B+树做索引呢？原来，哈希表存在以下几个问题：
第一，模糊查找不支持。如果我们想要查找名字中包含“小明”的所有人，哈希表无法实现。因为哈希表只能根据精确的哈希码定位到一个位置，而无法处理模糊性查找。
第二，范围查找不支持。如果我们要查找 ID 在 100 到 400 之间的人，哈希表也无能为力。因为哈希表只能处理等值查找，无法处理范围查找。
第三，哈希冲突问题。当多个索引字段映射成相同的哈希码时，就会产生哈希冲突。这时，哈希表会将这些索引字段存储在同一个位置上，形成一条长链表。这会导致查找效率下降，因为我们需要遍历整个链表才能找到对应的数据。
而 B+ 树则能够通过最左前缀原则快速找到对应的数据。同时，B+ 树的叶子节点是按顺序存储的，所以支持范围查找。B+ 树还可以设置分支节点和叶子节点的大小，可以控制每个节点所存储的数据量，从而优化查询性能。
综上所述，虽然哈希表也是一种高效的数据结构，但在构建索引时，B+树更加灵活和可靠，能够应对更多的查询场景，因此更受欢迎。
🔔如果您需要转载或者搬运这篇文章的话，非常欢迎您私信我哦~
