B+Tree索引树高度如何计算

by 夏泽民 Apr 1, 2020

一个表有3000万记录，假如有一列占8位字节的字段，根据这一列建索引的话索引树的高度是多少？
平时这也只关注MySQL索引一般都是都是用B+Tree来存储维护索引的，还有一些复合索引的最左匹配原则等等，还真没有实际关注过始即然用到索引能提升

查询的效率，那么这个索引树高是多少，给定表和索引字段后怎么计算出索引树的高度？下面将用举例的形式来说明如何计算索引树的高度。

在举例之前，先给出一个千万级记录表的索引的高度大概在3-5的样

假设：

表的记录数是N

每一个BTREE节点平均有B个索引KEY

那么B+TREE索引树的高度就是logN-B(等价于logN/logB)

由于索引树每个节点的大小固定，所以索引KEY越小，B值就越大，那么每个BTREE节点上可以保存更多的索引KEY，也就是B值越大，索引树的高度就越小，那么基于索引的查询的性能就越高。所以相同表记录数的情况下，索引KEY越小，索引树的高度就越小。

现在我们假设表3000W条记录（因为2^25=33554432），如果每个节点保存64个索引KEY,那么索引的高度就是（log2^25)/log64≈ 25/6 ≈ 4.17

通过上面的计算可知，要计一张表索引树的高度，只需要知道一个节点有多，从而就能知道每个节点能存储多少个索引KEY。现代数据库经过不断的探索和优化，并结合磁盘的预读特点，每个索引节点一般都是操作系统页的整数倍，操作系统页可通过命令得到该值得大小，且一般是4094，即4k。而InnoDB的pageSize可以通过命令得到，默认值是16k。

以BIGINT为例，存储大小为8个字节。INT存储大小为4个字节（32位）。索引树上每个节点除了存储KEY，还需要存储指针。所以每个节点保存的KEY的数量为pagesize/(keysize+pointsize)（如果是B-TREE索引结构，则是pagesize/(keysize+datasize+pointsize)）。

假设平均指针大小是4个字节，那么索引树的每个节点可以存储16k/((8+4)*8)≈171。那么：一个拥有3000w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log2^25)/log171 ≈ 25/7.4 ≈ 3.38。

假设平均指针大小是8个字节，那么索引树的每个节点可以存储16k/((8+8)*8)≈128。那么：一个拥有3000w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log2^25)/log128 ≈ 25/7 ≈ 3.57

由上面的计算可知：一个千万量级，且存储引擎是MyISAM或者InnoDB的表，其索引树的高度在3~5之间。

https://cloud.tencent.com/developer/news/373193

我们使用MySQL数据库的时候，绝大部分的情况下在使用InnoDB存储引擎，偶尔会使用MyISAM存储引擎，至于其他存储引擎，我相信大家都很少接触到，甚至可能都没有听说过。所以本文只讲解InnoDB和MyISAM两个存储引擎的索引，以及如何计算这两个存储引擎的索引结构B+Tree的高度。

InnoDB

InnoDB主键索引示意图如下，非叶子节点上没有实际的数据，只有叶子节点上才有实际的数据，并且叶子节点之间有指针串联指向下一个叶子节点，这样能够提升范围查询的效率：

InnoDB B+Tree主键索引示意图

InnoDB使用了聚簇索引（Clustered），即所有二级索引聚集在主键索引上，对InnoDB存储引擎表的任何访问，最终一定要搜索主键索引树，二级索引的示意图如下：

nnoDB B+Tree二级索引示意图

在InnoDB中，二级索引（所有不是主键索引的索引）上没有实际的数据，取而代之的是主键索引的值。这样的话，如果是基于二级索引的查询，会先在二级索引上搜索得到主键索引的值，然后再去主键索引树上搜索，得到最终的行数据。

这就意味着，至少有一次索引查找，可能会有两次索引查找，其中一定有一次主键索引查找。

所以，在InnoDB中，主键要设计的尽量小，主键越小，二级索引也会越小。满足需求的情况下，SMALLINT优先于INT，INT优先于BITINT，INTEGER类型优先于VARCHAR类型。如果主键用更大的数据类型，由于二级索引上有主键索引的值，那么不只是主键索引树变的更大更高，其他的二级索引树也会更大更高，这绝对是一个糟糕的做法。

MyISAM

MyISAM没有使用聚簇索引，所以主键就是一个普通的唯一索引，并且基于索引查询只会搜索当前索引，不会和其他索引有任何关系，任意两个索引之间互不影响。如下图所示，是MyISAM的主键索引示意图，我们可以看到，索引树的叶子节点上只有表中行数据的地址，而不是和InnoDB一样，有实际的数据：

MyISAM的主键索引示意图

如下图所示，是MyISAM的二级索引示意图，我们可以看到，其结构几乎和主键索引示意图一样，叶子结点上也有表中行数据的地址：

索引树的高度是一个非常重要的东西，因为当查找的条件能用到索引时，就不用全表扫描，而是只需要在索引上搜索，从索引的根节点到叶子节点。并且很明显的是：索引树越高，性能就会越差。我们假设在最糟糕的情况下，索引一点没有被加载到内存中，而是全部持久化在磁盘上。那么索引树有多高，就表示查询至少需要多少次IO操作。即使实际情况中，由于表的数据更多，索引也会很大，不大可能全部被保存在缓存中。而且如果是二级索引搜索，IO次数还要翻倍（二级索引搜索+主键索引搜索），这对性能是一个很大的影响。

这也是MySQL数据库使用B+Tree作为索引结构的原因：尽可能降低索引树的高度。而红黑树等其他数据结构，树的高度要深的多的多。

最后再总结一下影响索引树的高度：

表的行数：这很容易理解，表中的数据越多，索引就越大，索引树就越高。

索引列的大小：这个也很容易理解，一个INT或者BITINT类型的自增主键索引，相比CHAR(32)定长字符串索引，在表记录数相同的情况下，前者索引树要比后者更小，高度也更浅。因为前者的索引树是需要保存1、2、3、4、5、… …，而后者是保存c4ca4238a0b923820dcc509a6f75849b、c81e728d9d4c2f636f067f89cc14862c、eccbc87e4b5ce2fe28308fd9f2a7baf3、a87ff679a2f3e71d9181a67b7542122c、e4da3b7fbbce2345d7772b0674a318d5、… …。

当然可能还有其他因素会影响到索引的高度，但是这里提到的这两个因素，绝对是最重要的两个因素。

为什么BTree/B+Tree作为数据库或者文件索引效率很高
BTree有很多种分类，也可以说是基于BTree实现了其他类似BTree是结构，MySQL的默认索引方式为B+Tree，这里就从B+Tree的查找效率和计算机组成原理来讨论为什么BTree作为数据库索引效率很高，红黑树等数据结构也可以用来实现索引，为什么不选择这个结构？

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析BTree作为索引的效率。

从计算机组成原理的角度
主存存取原理
目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。

主存的存取过程如下：
当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。
写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。
这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理
上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

也就是说，程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，n个块的组合称为页，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

最小存储单元
扇区：磁盘的最小存储单位。扇区是块设备传输数据的基本单元，也就是说它是块设备中最小的寻址单位，扇区通常的大小为512B。
块：文件系统读写数据的最小单位。块是内核对文件系统的一种抽象，也就是说内核执行的所有磁盘操作都是以块为基本单位的。
页：内存的最小存储单位。

可以简单的将扇区和块理解为：扇区是硬件设备传输数据的最小单位，而块是操作系统传输数据的最小单位。一个块通常对应一个或多个相邻的扇区。一页的大小为磁盘块大小的2的n（n为正整数）次方倍。

总结：在计算机中，磁盘存储数据最小单元是扇区，一个扇区大小为512字节，而文件系统的最小存储单元是块，一个块的大小是4k（即如果一个文件及时只有1k，在磁盘上占的空间也是4k）。
说了这么多，我就是想表明InnoDB引擎的最小存储单元是页，一页默认值为16KB（MySQL5.5以前，一页固定为16k，MySQL5.5以后，页大小为4KB, 8KB, 或者16KB，MySQL5.7.6还支持32KB和64KB，但是默认情况下都是16KB，参见官网 https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_page_size ）。这个概念对后面计算InnoDB引擎中一棵B+Tree可以存放多少行数据很重要。

#getconf PAGE_SIZE
4096

一般的read()操作发生在应用程序提供的缓冲区与pagecache之间。而预读算法则负责填充这个pagecache。应用程序的读缓存一般都比较小，比如文件拷贝命令cp的读写粒度就是4KB；内核的预读算法则会以它认为更合适的大小进行预读I/O，比比如16-128KB。

BTree/B+Tree索引的性能分析

生成的索引结构是一个映射表存储在磁盘中，通常比较大，而索引文件的读取决于磁盘I/O的速度，计算机科学中有局部性原理与磁盘预读，数据库设计者正是巧妙地利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
除了利用磁盘预读原理外，mysql 把每个节点的空间大小设置为一个页还有一个原因是每个节点中的数据可能会分散到不同数据块中，因此把每个节点的空间大小设置为一个页，这样就能保证每个节点只需要一次IO。
这是一种以空间换时间的方法。

BTree中一次检索最多需要h-1（h为树的高度）次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用BTree作为索引结构效率是非常高的。而且d越大索引的性能越好，而出度的上限取决于节点内key和data的大小（因为一个节点占一页，通常是4k，所以要保证keysize+datasize+pointsize不超过4K，因此去掉datasize，d会更大）：

dmax=floor(pagesize/(keysize+datasize+pointsize))floor表示向下取整。

由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

从BTree/B+Tree查找的角度
上面提到BTree/B+Tree中一次检索最多需要h-1次I/O，这里肯定是需要从根节点开始搜索BTree/B+Tree，根节点就在内存中

当需要查找key为20的节点时：

先从内存中对更节点进行搜索找到下一个节点的指针，由于一个节点上的数据是有序的，因此可以用二分查找，定位到第二层坐左边的节点。
将该页的数据从磁盘上读取到内存，再按照二分查找定位到最后一层中间的节点。
从磁盘上读取该节点到内存中，找到20，取出数据
这一过程进行了2次I/O操作，3次内存查找操作，并且二分查找的时间复杂度为O(log2n)。
InnoDB引擎中一棵B+Tree可以存放多少行数据？
InnoDB引擎中的B+Tree结构在MySQL索引详解一文中已经讲解过

B+Tree中，一个节点设计为一个页的大小16K，假设一行记录的数据大小为nK，B+Tree的高度为t（t的值一般取1~3），主键的长度为p字节，指针大小在InnoDB源码中设置为6字节

先计算非叶子节点能存放多少个指针和键值的组合？

指针和键值的组合占p+6字节，因此答案是[16*1024]/（p+6）个，这个结果记为A

再把数的高度带入计算，得到InnoDB引擎中一棵B+Tree可以存放多少行数据？

答案是： (A ^t) *（16/n）

举例

一行记录的大小是1k，则一页能存16条记录，B+Tree高度是3，主键id设为bigint（8字节），一个节点最大能存16*1024=16384字节的数据，指针在InnoDB中是6字节，则主键+指针的大小是14字节，一个非叶子节点能存16384/14=1170个主键+指针的组合，因此对于高度为3的B+Tree，能存1170 * 1170 * 16=21902400条记录。

InnoDB引擎中为什么推荐使用自增整型主键
因为整型比较大小比字符串效率块，这样在B+Tree节点内查找的时候就会快点，并且整型存储空间一般也更小，bigint就8字节。而且InnoDB引擎使用的是带指针的B+Tree，即叶子节点用指针连起来，如果使用自增主键，新增记录时，直接在最后一个节点插入即可，增加了插入效率。否则在B+Tree中插入节点会导致节点分裂等影响效率的问题。

InnoDB引擎中为什么必须要指定主键（未指定会启用虚拟主键）
因为InnoDB擎中的数据表本身就是B+Tree结构存储数据和主键索引的（数据和索引存储在一起）。所以指定主键构建B+Tree结构的主键索引+数据文件提高查找效率

MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

文章主要内容分为三个部分。

第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

第三部分根据上面的理论基础，讨论MySQL中高性能使用索引的策略。

数据结构及算法基础
索引的本质
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

B-Tree和B+Tree
目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引，这一节先单纯从数据结构角度描述它们。

B-Tree
为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

d为大于1的一个正整数，称为B-Tree的度。
h为一个正整数，称为B-Tree的高度。
每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
所有叶节点具有相同的深度，等于树高h。
key和指针互相间隔，节点两端是指针。
一个节点中的key从左到右非递减排列。
所有节点组成树结构。
每个指针要么为null，要么指向另外一个节点。
如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)v(key1)，其中v(key1)v(key1)为node的第一个key的值。
如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)v(keym)，其中v(keym)v(keym)为node的最后一个key的值。
如果某个指针在节点node的左右相邻key分别是keyikeyi和keyi+1keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)。

关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，本文不打算完整讨论B-Tree这些内容，因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法，有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

B+Tree
B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

每个节点的指针上限为2d而不是2d+1。

内节点不存储data，只存储key；叶子节点不存储指针。

由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。

带有顺序访问指针的B+Tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

这一节对B-Tree和B+Tree进行了一个简单的介绍，下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。

为什么使用B-Tree（B+Tree）
上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

从结果中可以到titles表的主索引为<emp_no, title, from_date>，还有一个辅助索引。为了避免多个索引使事情变复杂（MySQL的SQL优化器在多索引时行为比较复杂），这里我们将辅助索引drop掉：

ALTER TABLE employees.titles DROP INDEX emp_no;
这样就可以专心分析索引PRIMARY的行为了。

首先我们看下title一共有几种不同的值：

SHOW PROFILES;
+———-+————+——————————————————————————-+
| Query_ID | Duration | Query |
+———-+————+——————————————————————————-+
| 10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no=’10001’ AND from_date=’1986-06-26’|
| 11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no=’10001’ AND title IN … |
+———-+————+——————————————————————————-+
“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据，则后者性能优势会更加明显。当然，如果title的值很多，用填坑就不合适了，必须建立辅助索引。

情况七：查询条件中含有函数或表达式。
很不幸，如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引（虽然某些在数学意义上可以使用）。例如：

索引选择性与前缀索引
既然索引可以加快查询速度，那么是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。

第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。至于多少条记录才算多，这个个人有个人的看法，我个人的经验是以2000作为分界线，记录数不超过 2000可以考虑不建索引，超过2000条可以酌情考虑索引。

另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：

Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。例如，上文用到的employees.titles表，如果title字段经常被单独查询，是否需要建索引，我们看一下它的选择性：

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
+————-+
| Selectivity |
+————-+
| 0.0000 |
+————-+
title的选择性不足0.0001（精确值为0.00001579），所以实在没有什么必要为其单独建索引。

有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。

从图12可以看到employees表只有一个索引，那么如果我们想按名字搜索一个人，就只能全表扫描了：

SELECT count(DISTINCT(first_name))/count() AS Selectivity FROM employees.employees;
+————-+
| Selectivity |
+————-+
| 0.0042 |
+————-+
SELECT count(DISTINCT(concat(first_name, last_name)))/count() AS Selectivity FROM employees.employees;
+————-+
| Selectivity |
+————-+
| 0.9313 |
+————-+

显然选择性太低，<first_name, last_name>选择性很好，但是first_name和last_name加起来长度为30，有没有兼顾长度和选择性的办法？可以考虑用first_name和last_name的前几个字符建立索引，例如<first_name, left(last_name, 3)>，看看其选择性：

SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.7879 |
+-------------+
选择性还不错，但离0.9313还是有点距离，那么把last_name前缀加到4：

SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
| 0.9007 |
+-------------+
这时选择性已经很理想了，而这个索引的长度只有18，比<first_name, last_name>短了接近一半，我们把这个前缀索引建上：

ALTER TABLE employees.employees
ADD INDEX `first_name_last_name4` (first_name, last_name(4));
此时再执行一遍按名字查询，比较分析一下与建索引前的结果：

SHOW PROFILES;
+----------+------------+---------------------------------------------------------------------------------+
| Query_ID | Duration | Query |
+----------+------------+---------------------------------------------------------------------------------+
| 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |
| 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |
+----------+------------+---------------------------------------------------------------------------------+
性能的提升是显著的，查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）。

InnoDB的主键选择与插入优化
在使用InnoDB存储引擎时，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。

经常看到有帖子或博客讨论主键选择问题，有人建议使用业务无关的自增主键，有人觉得没有必要，完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点，大多数论据都是业务层面的。如果从数据库索引优化角度看，使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。

如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页

这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。

如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：

此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此，只要可以，请尽量在InnoDB上采用自增字段做主键。

索引是 MySQL 数据库中的重要的数据结构之一，它是数据库性能调优技术的基础，常用于实现数据的快速检索。
索引就是根据表中的一列或若干列按照一定顺序建立的列值与记录行之间的对应关系表，实质上是一张描述索引列的列值与原表中记录行之间一一对应关系的有序表。
在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
MySQL数据访问方式
在 MySQL 中，通常有以下两种方式访问数据库表的行数据：

顺序访问
顺序访问是在表中实行全表扫描，从头到尾逐行遍历，直到在无序的行数据中找到符合条件的目标数据。
实现方式简单，但是效率低。
索引访问
索引访问时通过遍历索引来访问表中记录行的方式。使用这种方式的前提是对表建立一个索引，在列上创建了索引之后，查找数据时可以直接根据该列上的索引找到对应记录行的位置，从而快捷地查找到数据。索引存储了指定列数据值的指针，根据指定的排序算法对这些指针排序。
我用了一张大小为3.22M大小，有22527行数据的表做了一个简单的测试，number字段被设置为索引，type_number是和number字段同类型的字段，分别以这两个字段为条件查询
索引的类型
（1）常规索引（normal）

MySQL中默认的索引类型，没有任何限制。
创建索引：
CREATE INDEX indexName ON mytable(username(length));
如果是CHAR，VARCHAR类型，length可以小于字段实际长度；如果是BLOB和TEXT类型，必须指定 length。
添加索引：
ALTER table tableName ADD INDEX indexName(columnName)
创建表的时候直接指定：
2）唯一索引（UNIQUE）

列值必须唯一，但是可以有一个null值。
创建索引：
CREATE UNIQUE INDEX indexName ON mytable(username(length));
添加索引：
ALTER table mytable ADD UNIQUE [indexName] (username(length))
创建表的时候直接指定：
（3）全文索引（FULLTEXT）

MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引；
MySQL 5.6 及以后的版本，MyISAM 和 InnoDB 存储引擎均支持全文索引;
只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。

CREATE FULLTEXT INDEX indexName ON mytable(username(length));

（4）主键索引

不允许重复，不允许空值，主键id默认的索引类型。一般创建表的时候设置了主键，则默认给该主键设置主键索引。

（5）组合索引

用多个列组合构建的索引，这多个列中的值不允许有空值，使用最左匹配原则。

删除索引：

DROP INDEX [indexName] ON mytable;
（6）覆盖索引
一个包含查询所需字段的索引称为“覆盖索引”，如select a,b from table1 where c=1;
建立联合索引（a, b, c），这样MySQL只需要通过索引就可以返回查询所需要的数据，而不必在查到索引之后进行回表操作，减少IO，提高了效率。

MyISAM和InnoDB引擎实现的索引结构不同，MyISAM实现了非聚簇索引，InnoDB实现了聚簇索引。
按照索引的键是否为主键来分为“主索引”和“辅助索引”，使用主键键值建立的索引称为“主索引”，其它的称为“辅助索引”。因此主索引只能有一个，辅助索引可以有很多个。

MyISAM实现的非聚簇索引

非聚簇索引顺序与数据物理排列顺序无关。
非聚簇索引的主索引和辅助索引几乎是一样的，只是主索引不允许重复，不允许空值，他们的叶子结点的key都存储指向键值对应的数据的物理地址。
非聚簇索引的数据表和索引表是分开存储的。
MyISAM引擎使用带有顺序访问指针的B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

InnoDB实现的聚簇索引

聚簇索引的顺序就是数据的物理存储顺序。
聚簇索引的主索引的叶子结点存储的是键值对应的数据本身，辅助索引的叶子结点存储的是键值对应的数据的主键键值。因此主键的值长度越小越好，类型越简单越好。
聚簇索引的数据和主键索引存储在一起。
聚簇索引的数据是根据主键的顺序保存。
聚簇索引和非聚簇索引的差异
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
（1）
第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。**因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），**如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
（2）
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域

聚簇索引和非聚簇索引小结
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非常单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

索引的使用原则
下文提到的索引是否被使用，可以在查询语句前加explain然后分析结果
（1）最左匹配原则
组合索引中提到过最左匹配原则，即对于组合索引，where后面的条件可以不是组合索引中的每一项，只要查询的条件中用到了最左边的索引列,索引就会被使用。
比如
create index index_a1_a2 on user(a1,a2);
执行
select * from user where a1 = 1
组合索引index_a1_a2会生效
执行
select * from user where a2 = 1
组合索引index_a1_a2不会生效
（2）通配符%不能位于首位
create index index_name on user(name);
这个查询语句中，index_name不会生效

explain select * from user where name like '%张';
1
这个查询语句中，index_name会生效

explain select * from user where name like '张%';
1
（3）大文本的索引
如果对大的文本进行搜索,使用全文索引而不是使用like
（4）or条件的索引使用原则
如果or前的条件中的列有索引,而后面的列中没有索引,那么涉及到的索引都不会被用到。也就是or的左右条件都应该是索引列
（5）字符型要用’'
如果是字符型，传入的是数字，必须加上’'把数字引起来索引才会起作用
（6）!=/<>上使用索引无效
从B+Tree的结构上看，是不支持!=索引的。

索引的选取
本部分参考：https://blog.csdn.net/u012954706/article/details/81241049

越小的数据类型通常更好：越小的数据类型通常在磁盘、内存和CPU缓存中都需要更少的空间，处理起来更快。
简单的数据类型更好：整型数据比起字符，处理开销更小，因为字符串的比较更复杂。
尽量避免NULL：应该指定列为NOT nuLL,在MySQL中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。
不适合创建索引的场景
在查询中很少使用的列，因为对很少使用的列建立索引反而会降低了系统的维护速度和增大了空间需求。
对于那些只有很少数据值的列也不应该增加索引。因为本来结果集合就是相当于全表查询了，所以没有必要。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。
对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。或者建立称全文索引。
当修改性能操作的表大于检索操作时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。
适合创建索引的字段
表的主键、外键必须有索引；外键是唯一的，而且经常会用来查询

数据量超过300的表应该有索引
经常与其他表进行连接的表，在连接字段上应该建立索引；经常连接查询，需要有索引（MySQL5.6后自动为外键建立索引）
经常用到排序的列上，因为索引已经排序
经常用在范围内搜索的列上创建索引，因为索引已经排序了，其指定的范围是连续的
索引的优缺点
优点
提高查询速度
缺点
创建和维护索引需要耗费时间
降低更新和写入速度
费磁盘空间

HashMap为什么底层不选用AVL树:
AVL树是一棵严格的平衡树，它所有的子树都满足二叉平衡树的定义。因此AVL树高被严格控制在XXX，因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。

红黑树用非严格的平衡来降低插入删除时旋转的次数,最长路径长度不超过最短路径长度的2倍。

因此，如果你的业务中查找远远多于插入、删除，那选AVL树；
如果查找、插入、删除频率差不多，那么选择红黑树。

红黑树5个性质：
1.根节点为黑色节点

2.红色节点不能连续，也就是红色节点的孩子节点和父节点都不能是红色节，红色节点的孩子节点一定是黑色节点。

3.叶子节点一定是黑色（也就是空节点）

4.每一个节点到叶子节点的黑色节点的个数都是相同的

5.新插入的节点一定是红色

主要是插入过程：（最多需要两次旋转就可以达到红黑树平衡，主要是通过变色来代替了一部分旋转，但是变色的代价是很低的）
1.如果插入的节点父节点是黑色直接插入

2.插入节点的是红色，就改变父节点（红色变为黑色）和祖父节点（黑色变为红色）,可能有时候父节点的兄弟节点也要变色。

这个时候一般会出现冲突，那么我们先旋转，再看是否颜色仍然冲突，如果仍然冲突，我们就改变冲突节点的父节点和祖父节点。再进行同样的操作。

参考：

https://www.cnblogs.com/CarpenterLee/p/5503882.html

删除过程，假如要删除节点p：（最多只用旋转3次就能删除一个节点）
只有删除点是BLACK的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束

假如p的左右节点都为空，就直接删除这个节点p

假如p的左或者右节点不为空，那么我们就是要找到这个节点后继。

1.t的右子树不空，则t的后继是其右子树中最小的那个元素。

2.t的右孩子为空，则t的后继是其第一个向左走的祖先。

那么我们接下来删除p节点，用t代替p，再去用上面的操作重复删除t的这样一个操作（在这个过程中我们会有旋转也会有颜色的变化）。

参考：

https://www.cnblogs.com/CarpenterLee/p/5525688.html

B-树的性质：
一棵m阶B-树

1.根结点至少有两个子女；

2.每个非根节点所包含的关键字个数最多m-1个

3.所有关键字分布在整颗树中

4. 任何一个关键字只能分布在一个节点中

5.搜索有可能在非叶子节点结束

B+树的性质：
1.有n棵子树的结点中含有n个关键字；

2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。

3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字

对于B+树的搜索：

B+树的头指针有两个，一个指向根节点，另一个指向关键字最小的元素，因此B+树有两种遍历的方式：

1. 从根节点开始随机查询

2.从最小关键词顺序查询

对于一个m路B+树：
它的深度应该是logceil（m/2）n到logm n之间

在选择数据库索引的时候很大一个因素是减少读写磁盘

页表的目的是扩展内存+加速磁盘读写。一个页（Page）通常4K（等于磁盘数据块block的大小，见inode与block的分析），从磁盘读写的角度出发，操作系统每次以页为单位将内容从磁盘加载到内存（以摊分寻道成本），修改页后，再择期将该页写回磁盘。考虑到页表的良好性质，可以使每个节点的大小约等于一个页（使m非常大），这每次加载的一个页就能完整覆盖一个节点，以便选择下一层子树；对子树同理。对于页表来说，AVL（或RBT）相当于1个key+2个子树的B树，由于逻辑上相邻的节点，物理上通常不相邻，因此，读入一个4k页，页面内绝大部分空间都将是无效数据。

假设key、子树节点指针均占用4B，则B树节点最大m * (4 + 4) = 8m B；页面大小4KB。则m = 4 * 1024 / 8 = 512，一个512叉的B树，1000w的数据，深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如AVL的深度为log(2)(10^7) = 23.25 ~= 24，相差了5倍以上。震惊！B树索引深度竟然如此！

https://monkeysayhi.github.io/2018/03/06/%E6%B5%85%E8%B0%88MySQL%E7%9A%84B%E6%A0%91%E7%B4%A2%E5%BC%95%E4%B8%8E%E7%B4%A2%E5%BC%95%E4%BC%98%E5%8C%96/
为什么数据库不采用普通的AVL树？
普通的二分查找，二叉树可以把速度提升到O(log(n,2))，查询的瓶颈在于树的深度，最坏的情况要查找到二叉树的最深层，由于，每查找深一层，就要访问更深一层的索引文件。在多达数G的索引文件中，这将是很大的开销。所以，尽量把数据结构设计的更为‘矮胖’一点就可以减少访问的层数。所以就想到了B+，B-树。

为了减少磁盘IO，我们需要进行进行磁盘预读，普通的AVL树一个节点都只有一个关键字，不适合进行磁盘预读。

因此我们需要多路平衡树的存在，就可以充分利用磁盘预读，每个节点（一个页记录）都有多个关键字，那么我们磁盘IO的次数会减少。

为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引？
1.B+树的磁盘读写代价更低
B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多（也就是一个页记录，B+树页记录的关键字的个数比B-树一个节点存的关键字个数更多），一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2.B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3.B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了（叶子节点层还维护了一个链表），B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因

Category storage