2024-08-30

为何使用B+树作为索引的数据结构

1)二叉树与B/B+树具有相同的查找时间复杂度O(logn)，所以时间复杂度不是选择B树的原因
2)二叉树未能很好的应用磁盘的预读功能（每次磁盘预读的数据都是无用的），会造成较多的磁盘I/O操作；B /B+树都很好的运用了磁盘的预读功能，磁盘页的大小与节点的大小一致（InnoDB为16kb），减少了磁盘的I/O操作。

3)其中，对于B+树，又通过指针将叶子结点链接了起来，对于范围查找十分有效
4)B+ /B 树节点的个数也较二叉树有所增多，可以减少节点的查找次数

二叉树：

二叉搜索树的特点：每个节点的左儿子小于父节点，父节点又小于右儿子。时间复杂度是O(logn)。
多叉搜索树的特点：每个节点有多个儿子，儿子之间的大小保证从左到右递增。

二叉树搜索效率高，但是实际上大多数的数据库存储却并不使用O(n)，其原因是

索引不止存在内存中，还要写到磁盘上。树存储在磁盘中的，访问每个节点,都对应一次磁盘I/O（假设每个节点大小< 操作系统的最小读写单位块大小），即树的高度=每次查询时磁盘I/O操作次数，树越高越影响性能，而数据越多，树高不断增长，磁盘I/O越多，性能越差。

一棵100万节点的平衡二叉树，树高20。一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10 ms左右的寻址时间。对于一个100万行的表，单独访问一行可能需要 20×10 ms的时间。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。即使用多叉树，减少树高。
二叉查找树存在一个极端的情况：每次插入都是二叉查找树中最大的元素，二叉查找树就会退化成一条链表，查找数据的时间复杂度变为O(n)

自平衡二叉树：

在二叉查找树基础上增加了约束：每个节点的左子树和右子树的高度差不能超过1。即增加元素时它会维持自平衡，节点的左子树和右子树仍然为平衡二叉树，查询的时间复杂度维持在O(logn)。还有很多自平衡二叉树，比如红黑树，它的操作就比较复杂了。

无论平衡二叉树还是红黑树，每个节点只能有2个子节点，随着元素的增加，树高都会随之增加，意味着磁盘I/O操作次数随之变多，查询效率变低。

BTree：

节点：指树中的一个元素（图中的一个框）

节点的度：节点拥有的子树的个数，二叉树的度不大于2

叶子节点：度为0的节点，也称之为终端结点

高度：叶子结点的高度为1，叶子结点的父节点高度为2，以此类推，根节点的高度最高

BTree又叫自平衡多叉查找树，也称B-树。允许M个子节点（M>2），从而降低树高。

B树的每个节点最多可以包括M个子节点，M称为B数的阶，所以B树是个多叉树。

例如：

一个3阶B树，每个节点最多2个数据（M-1个，方便比较大小，以此找到对应子节点），和最多3个子节点(M个)，超过就会分裂节点。

每个节点的组成：
1）索1) 索引：索引值(如id)
2)数据：索引值对应的data
3)指针：该层没有指定索引，通过指针到下一层寻找
每个节点的大小：索引大小（如5B） + 数据大小（如95B）
每个节点的大小设置为一个页的大小，这样每个节点只需要一次IO就可以完全载入。
度比较大，每个节点可以存储多个索引值和数据，度越大，树的高度越低，磁盘IO的次数就越少
度 = 页的大小/(索引大小+数据大小)
叶子节点具有相同的深度，叶节点的指针为空，查询效率比较稳定

BTree和二叉树相比，查询数据的效率更高，因为对于相同的数据量来说，层级结构小，因此搜索速度快。

B+Tree

B+ 树在B树的基础上做了升级，MySQL索引的数据结构就采用的B+ 树。

结构差异：

叶子节点才会存放实际数据（索引+记录），非叶子节点只存放索引。
所有索引都会在叶子节点中出现，叶子节点间构成一个有序的链表。
非叶子节点的索引会同时存在于子节点中，且是子节点中最大或最小的索引。
非叶子节点有多少个子节点，其中就有多少个索引。

由于 B+Tree只有叶子节点保存data，因此查询任何key都要走到叶子节点。

性能区别：

单点查询

B树所有节点都可以映射数据，B+ 树只有叶子节点可以映射数据。B树查询最快O(1)，平均时间比B+稍快，但因为非叶子节点即存数据又存索引，查询可到达叶子节点和飞叶子节点，波动大。相比于B树，B+树非叶子节点仅存放索引，可以存储更多的索引，因此B+树可以更矮胖，查询底层节点的磁盘I/O操作次数更少。

插入、删除效率

B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），比如删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点。这样删除非常快。B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂。比如删除根节点中的数据，可能涉及复杂的树的变形。

B+ 树的插入也是一样，有冗余节点，插入可能存在节点的拆分（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要更多复杂的算法，类似红黑树的旋转操作等。

因此，B+ 树的插入和删除效率更高。

范围查询

B+ 树所有叶子节点间有一个链表进行连接，这种设计对范围查找非常有帮助。而B树没有，只能通过树遍历来完成范围查找，涉及多个节点的磁盘I/O操作。范围查询效率不如B+树。

InnoDB中的B+Tree

B+树的叶子节点间以双向链表连接，即能向左也能向右遍历。
节点内容是数据页，数据页中存放用户记录以及各种信息，每个数据页默认大小16KB。

主键索引也被称为聚簇索引（clustered index），也叫作聚集索引。其余都称呼为非主键索引也被称为二级索引（secondary index），也叫作辅助索引。

非叶子节点：存储了索引和子树节点的指针

叶子节点：叶子节点之间通过指针相互连接，存储了索引、数据、链表指针和指向记录的指针

索引分类：

按存储方式区分：B树索引，哈希索引

按逻辑区分：1.普通索引 2.少数索引 3.主键索引 4. 空间索引 5.全文索引

按实际使用区分：单列索引，多列索引

索引中保存了数据列的值和指向它们所在行的指针，所以在回表查询时，能快速定位到表中的特定行，从而提高查询效率。

为什么索引建立太多会导致写入和删除的效率下降？

索引过多会增加写入操作的开销

进行写操作时，数据库需要维护索引的更新，索引过多会导致维护开销变得非常大，使得写入操作变慢。
索引过多会占用大量磁盘空间

在创建索引时，数据库会为每个索引分配磁盘空间，就会占用大量的磁盘空间，导致磁盘空间不足，影响数据库的正常运行。
索引过多会降低查询效率

虽然索引能够提高查询效率，但查询时需要扫描所有的索引，而索引过多会导致扫描的时间变长，从而降低查询效率。
索引过多会导致缓存失效

数据库会将经常使用的数据缓存到内存中，以加快查询速度。但缓存的空间有限，索引过多就会挤占数据缓存的空间，导致数据缓存失效，从而降低查询效率。
索引过多会导致锁竞争

在进行查询操作时，数据库会对相关的数据进行锁定，以保证数据的一致性。但是索引过多会导致锁竞争，因为每个索引都需要进行锁定，从而导致锁的竞争变得激烈，影响数据库的性能。
索引过多并且设置成联合索引会造成数据重复的交换

例如：当同一张表中ID字段为唯一字段，card和name为不唯一，同时将ID、card和name设置为联合主键，当card和name相同，而之前推送过数据下次推送就会因为联合索引的查询不同，造成数据的重复推送！

综上所述，创建索引时需要谨慎考虑，避免过多的索引导致数据库性能下降。