文章目录
- 什么是索引
- 索引类型
- 索引的数据结构
- Hash索引
- 有序数组
- 二叉搜索树
- 平衡二叉树
- B树
- B+索引
- 索引使用规则
- 索引失效的情况
- 如何选择正确的列进行索引？
什么是索引
索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。
索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快，可快速访问数据库表中的特定信息。
索引类型
主键索引：数据列不允许重复，不允许为NULL，一个表只有一个主键。
唯一索引：数据列不允许重复，允许为NULL，一个表允许多个列创建唯一索引。
普通索引：基本的索引类型，没有唯一性的限制，允许为NULL值。
全文索引：是目前搜索引擎使用的一种关键技术，对文本的内容进行分词、搜索。
覆盖索引：查询列要被创建的索引覆盖，不必读取数据行。
组合索引：多列值组成一个索引，用于组合搜索，效率大于索引合并。
聚簇索引：索引项的排序方式和表中的数据记录排序方式一直的索引。也就是说聚簇索引的顺序就是数据的物理存储顺序。
非聚簇索引：索引数据和物理存储顺序不同。
索引的数据结构
Hash索引
1.仅仅能满足"=",“IN"和”<=>"查询，不能使用范围查询
2.其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引
3.只有Memory存储引擎显示支持hash索引
有序数组
为了解决区间查询速度慢的问题，有序数组应运而生。它的等值和范围查询都很快。还是上面根据id号找用户的例子，这时候的索引结构是这样的：
有序数组在查询方式比较快，但是涉及删除，插入的情况下，效率比较低，所以根据情况来使用。
二叉搜索树
二叉搜索树，也称二叉查找树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的二叉树：每个节点只有两个分叉，左子树所有节点值比右子树小，每个节点的左、右子树也是一个小的二叉树，且没有健值相等的节点。
之所以设计成二叉有序的结构是因为可以利用二分查找法，它的插入和查找的时间复杂度都是 O(log(N))，但是最坏情况下，它的时间复杂度是 O(n)，原因是在插入和删除的时候树没有保持平衡。比如顺拐的二叉树
平衡二叉树
平衡二叉树也叫 AVL 树，它与二叉查找树的区别在于平衡，它任意的左右子树之间的高度差不大于 1**。
根据平衡二叉树的特点。它的查询时间复杂度是 O(log(N))，当然为了维护平衡它更新的时间复杂度也是 O(log(N))。貌似完美？但是还有问题。
学过数据结构都知道，时间复杂度与树高相关。你想想假设现在有一颗 100 万节点的平衡二叉树，树高 20。一次查询需要访问 20 个数据块。而根据计算机组成原理得知，从磁盘读一个数据快平均需要 10ms 的寻址时间。PS：索引不止存在内存中，还会写到磁盘上，所以优化的核心在于减少磁盘的 IO 次数。
B树
每个非叶子节点并且非根节点最少有 m/2 个（向上取整），即内部节点的子节点个数最少也有 m/2 个。
根节点至少有两个子节点，每个内节点（非叶子节点就是内节点）最多有 m 个分叉。
B 树的所有节点都存储数据，一个节点包含多个元素，比如健值和数据，节点中的健值从小到大排序。
叶子节点都在同一层，高度一致并且它们之间没有指针相连。
存在的问题：
1.叶子节点无指针相连，所以范围查询增加了磁盘 IO 次数，降低了查询效率。
2.如果 data 存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘 IO 次数就会变大。
B+索引
由上图得知，B+ 树的数据都存放在叶子节点上。所以每次查询我们都需要检索到叶子节点才能把数据查出来。有人说了，那这不变慢了吗？B 树不一定要检索到叶子节点呀。
其实不然，因为 B+ 的非叶子节点不再存储数据。所以它可以存更多的索引，也即理论上 B+ 树的树高会比 B 树更低。从这个角度来说，与其为了非叶子结点上能存储值而选择 B 树，倒不如选择 B+ 树，降低树高。
B+树的特点：
1.所有数据都存储在叶子节点：在B+树中，所有的数据记录节点都是按顺序存放在叶子节点中，并且叶子节点之间是相互链接的。
2.内部节点不存储数据：与B树不同，B+树的内部节点只存储键值（keys）和指向子节点的指针，不存储实际的数据记录。
3.更宽的节点：B+树的节点可以有更多的键值，因此每个节点可以有更多子节点，这减少了树的高度，使得查找操作更快。
4.顺序访问性能好：由于数据都存储在叶子节点，并且叶子节点之间相互链接，B+树非常适合进行顺序访问操作。
5.动态有序数组：B+树的叶子节点可以看作是一个动态有序数组，这使得数据的插入和删除操作更加高效。
B+树优化查询性能：
1.减少磁盘I/O操作：数据库索引通常存储在磁盘上，而B+树的结构使得查询操作可以减少磁盘I/O次数。由于B+树的高度较低，查找数据时需要访问的节点数量较少，从而减少了磁盘访问次数。
2.顺序访问优化：B+树的叶子节点相互链接，形成了一个有序的数据链表。这种结构非常适合顺序访问操作，如范围查询和全表扫描，因为可以快速地从一个数据记录移动到下一个数据记录。
3.高效的查找算法：B+树的查找操作类似于二分查找，可以在对数时间复杂度内完成。从根节点开始，通过比较键值和指针，快速定位到叶子节点，然后找到具体的数据记录。
4.局部性原理：由于B+树的节点较大，可以存储更多的键值和指针，这增加了数据在内存中的局部性。当一个节点被加载到内存中时，与其相邻的节点也很可能被加载，这有助于缓存命中率的提高。
5.动态平衡：B+树是自平衡的，这意味着在插入和删除操作后，树会通过分裂和合并节点来保持平衡。这种动态平衡确保了树的高度不会变得过高，从而保持了查询性能。
6.空间效率：B+树的内部节点不存储数据记录，只存储键值和指针，这使得每个节点可以存储更多的键值，减少了节点数量，提高了空间效率。
7.批量加载：由于B+树的叶子节点形成了一个有序链表，数据库可以一次性加载多个相邻的数据记录，这对于批量处理和分析操作非常有用。
8.支持多种查询类型：B+树不仅支持点查询，还支持范围查询和顺序查询，这使得它在处理复杂查询时更加灵活和高效。
9.并发控制：在多用户环境中，B+树可以通过锁机制来支持并发操作，确保数据的一致性和完整性。
10.适应性：B+树可以根据数据的分布和查询模式进行调整，以优化性能。例如，数据库系统可以根据查询的频率和类型来调整B+树的节点大小和结构。
package com.schdule.util;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Node {
List<Integer> key;
List<Node> children;
boolean isLeaf;
Node next;
/**
* 构造函数
* @param isLeaf
*/
public Node(boolean isLeaf){
this.isLeaf=isLeaf;
this.key=new ArrayList<>();
this.children=new ArrayList<>();
this.next=null;
}
class BPlusTree{
private static final int ORDER=4;
private Node root;
/**
* 构造函数
*/
public BPlusTree() {
}
/**
* 超找合适的叶子节点
*/
public Node findLeaf(int key){
Node current=root;
while (!current.isLeaf){
int i=0;
while(i<current.key.size() && key>=current.key.get(i)){
i++;
}
current=current.children.get(i);
}
return current;
}
/**
* 插入操作
*/
public void insert(int key){
Node leaf=findLeaf(key);
leaf.key.add(key);
Collections.sort(leaf.key);
//如果叶子节点的键值超过了阶数，需要分裂
if(leaf.key.size()>=ORDER){
splitLeafNode(leaf);
}
}
/**
* 分裂叶子结点
* @param leaf
*/
public void splitLeafNode(Node leaf){
int midIndex=leaf.key.size()/2;
Node newLeaf=new Node(true);
//将一半的键值移到新的叶子结点
newLeaf.key.addAll(leaf.key.subList(midIndex,leaf.key.size()));
leaf.key=new ArrayList<>(leaf.key.subList(0,midIndex));
//链接新旧叶子节点
newLeaf.next=leaf.next;
leaf.next=newLeaf;
if(leaf==root){
//如果叶子结点是根节点，需要创建一个新的根节点
Node newRoot=new Node(false);
newRoot.key.add(newLeaf.key.get(0));
newRoot.children.add(leaf);
newRoot.children.add(newLeaf);
root=newRoot;
}else{
//如果不是根节点，需要把新叶子节点的第一个键值上移到父节点
insertIntoParent(leaf,newLeaf.key.get(0),newLeaf);
}
}
/**
* 将分裂的值插入到父节点
* @param leftNode
* @param key
* @param rightNode
*/
public void insertIntoParent(Node leftNode,int key,Node rightNode){
Node parent=findParent(root,leftNode);
int insertIndex=0;
while (insertIndex<parent.key.size() && key>parent.key.get(insertIndex)){
insertIndex++;
}
parent.key.add(insertIndex,key);
parent.children.add(insertIndex+1,rightNode);
//如果父节点的键值数超过了阶数，需要分裂
if(parent.key.size()>=ORDER){
splitInternalNode(parent);
}
}
/**
* 分裂内部节点
* @param node
*/
public void splitInternalNode(Node node){
int midIndex=node.key.size()/2;
Node newNode=new Node(false);
newNode.key.addAll(node.key.subList(midIndex+1,node.key.size()));
newNode.children.addAll(node.children.subList(midIndex+1,node.children.size()));
node.key = new ArrayList<>(node.key.subList(0, midIndex));
node.children = new ArrayList<>(node.children.subList(0, midIndex + 1));
if (node == root) {
// 如果节点是根节点，需要创建一个新的根节点
Node newRoot = new Node(false);
newRoot.key.add(node.key.get(midIndex));
newRoot.children.add(node);
newRoot.children.add(newNode);
root = newRoot;
} else {
// 把分裂出来的中间值上移到父节点
insertIntoParent(node, node.key.get(midIndex), newNode);
}
}
/**
* 查找父节点
* @param current
* @param child
* @return
*/
public Node findParent(Node current,Node child){
if(current.isLeaf || current.children.get(0).isLeaf){
return null;
}
for (Node node : current.children) {
if(node==child || node.children.contains(child)){
return current;
}else{
Node parent=findParent(node,child);
if(parent != null){
return parent;
}
}
}
return null;
}
public boolean search(int key){
Node leaf=findLeaf(key);
if(leaf.key.contains(key)){
return true;
}else{
return false;
}
};
}
}
索引使用规则
索引失效的情况
索引失效是指数据库查询中索引无法有效地加速查询或查询不使用索引，从而导致性能下降。索引失效通常是由查询语句、数据分布或索引设计等多种因素引起的。以下是一些常见的索引失效原因以及如何避免它们：
- 列没有索引： 如果查询中涉及的列没有索引，将无法使用索引加速查询。
• 避免方法： 确保对查询中经常使用的列创建适当的索引，根据查询需求选择单列索引或复合索引。 - 使用函数或表达式： 如果在查询中对列使用函数、表达式或计算，索引可能无法生效。
• 避免方法： 尽量避免在索引列上使用函数或表达式。如果必须使用，可以考虑创建函数索引（函数索引是对表达式的索引）。 - 使用通配符开头的模糊搜索： 查询中使用LIKE 'pattern%'形式的模糊搜索时，索引通常无法用于查找匹配项。
• 避免方法： 如果需要模糊搜索，尽量避免通配符开头，可以考虑使用’pattern%'来进行模糊搜索，以允许索引的使用。 - 使用OR条件： 在查询中使用多个OR条件，每个条件涉及不同的列，可能导致索引失效。
• 避免方法： 尽量使用AND条件来替代OR条件，或者考虑将多个列的索引合并成一个复合索引。 - 数据分布不均匀： 如果数据在索引列上分布不均匀，索引可能无法提供足够的性能提升。
• 避免方法： 定期重新组织表，确保数据分布较均匀。对于自增ID等列，确保插入的数据不会导致数据分布的不均匀。 - 数据表太大： 当数据表非常大时，即使有索引，也可能无法显著提高查询性能。
• 避免方法： 对大型表进行分区或考虑使用分表策略，以减小每个查询的数据集。 - 不合理的索引设计： 选择不合理的索引、创建过多的索引或创建不必要的索引也可能导致索引失效。
• 避免方法： 仔细规划索引，确保每个索引都服务于特定类型的查询。避免不必要的索引。 - 没有统计信息： MySQL依赖于统计信息来优化查询计划，如果没有更新统计信息，查询可能会选择不合适的索引。
• 避免方法： 定期更新统计信息，以确保优化器能够做出正确的决策。
要避免索引失效，需要综合考虑查询设计、索引设计和数据维护。了解查询需求，选择合适的索引列，维护数据分布，并定期监控查询性能，以及时发现并解决索引失效问题，都是保持数据库高性能的关键步骤。
如何选择正确的列进行索引？
选择正确的列进行索引是优化数据库性能的关键步骤。错误的索引选择可能导致性能下降和额外的存储开销。以下是一些关于如何选择正确列进行索引的指导原则：
- 考虑查询频率：
• 选择那些经常用于查询条件的列进行索引。如果某个列经常用于WHERE子句、JOIN条件或ORDER BY子句，那么它通常是一个好的索引候选者。 - 考虑列的选择性：
• 索引的选择性是指索引列的唯一性程度。选择性越高，索引的效果越好。如果一个列的值几乎都不重复，那么在该列上创建索引可能不会带来太大性能提升。 - 考虑查询性能提升：
• 索引不仅用于过滤数据，还可以加速排序和连接操作。如果您经常进行排序或连接操作，考虑在相关列上创建索引。 - 小心过多的索引：
• 不要过度索引表，因为每个索引都需要额外的存储空间和维护成本。过多的索引可能会降低插入、更新和删除操作的性能。 - 组合索引：
• 对于包含多个查询条件的查询，考虑创建组合索引。组合索引可以涵盖多个列，并且在满足查询条件时更有效。 - 主键和外键：
• 主键列自动创建主键索引，外键列也可以考虑创建索引以加速连接操作。 - 考虑全文搜索和空间搜索：
• 对于需要全文搜索或空间搜索的查询，选择适当的列创建全文索引或空间索引。 - 定期评估和优化：
• 数据库的查询模式可能会随时间变化，因此需要定期评估索引的效能并根据需要进行优化和调整。 - 使用数据库性能工具：
• 使用数据库性能分析工具来识别潜在的查询瓶颈和缺乏索引的情况。这些工具可以提供有关哪些查询需要索引的有用信息。 - 测试和监控：
- 在生产环境之前，务必在测试环境中测试索引，以确保它们对查询性能的影响是积极的。在生产环境中定期监控索引的使用和性能。
总之，选择正确的列进行索引需要综合考虑查询需求、数据模式和性能目标。合理的索引策略可以显著提高数据库性能并降低查询时间，但需要谨慎选择索引列，避免不必要的索引，以确保维护数据库的高效性。
