索引的数据结构——B-tree / B + tree

我们知道查询是最重要的功能之一. 我们都希望查询数据的速度能够尽可能快，因此系统的设计人员将从查询算法的角度进行优化. 那么什么查询算法可以使查询更快？

1. 顺序搜索

最基本的查询算法当然是顺序搜索，这是一种比较每个元素的方法，但是当数据量很大时，该算法效率极低.

数据结构: 有序或无序队列

复杂度: O（n）

缺点: 检索效率低

2. 二进制搜索

比顺序搜索更快的搜索方法应该是二进制搜索. 二进制搜索的原理是，搜索过程从数组的中间元素开始. 如果中间元素恰好是要搜索的元素，则搜索过程结束；否则，搜索过程结束. 如果确定如果特定元素大于或小于中间元素，则在大于或小于中间元素的数组的一半中进行搜索，然后像以前一样从中间元素开始比较. 如果数组在特定步骤为空，则意味着找不到该数组.

示例代码:

int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

数据结构: 有序数组

复杂度: O（logn）

缺点: 所有元素都需要排序

3. 二进制搜索树搜索

二分搜索树的特征是:

如果其左子树不为空，则左子树上所有节点的值均小于其根节点的值;

如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值；

左右子树也是二叉搜索树.

二叉搜索树！ [在这里写图片描述]（）红黑树（自平衡二进制搜索树）

搜索原则:

如果b是一棵空树，则搜索失败，否则:

如果x等于b的根节点的数据字段的值，则搜索成功；否则，否则:

如果x小于b的根节点的数据字段的值，则搜索左子树；否则:

找到正确的子树.

但是，在数据存储中，由于树的深度，红树和黑树的磁盘IO读和写操作经常过于频繁，从而导致效率低下. 为什么会出现这种情况，首先我们要知道要获取磁盘上的数据，首先必须通过磁盘移动臂移动到数据所在的圆柱体，然后找到指定的磁盘表面索引的结构，然后将磁盘表面旋转到找到数据所在的轨道，最后读取和写入数据. 磁盘IO的成本主要花费在搜索所需的柱面上. 过多的树深度会导致频繁的磁盘IO读写. 因此，我们需要通过更好的树结构来尽可能降低树的高度.

数据结构: 二进制搜索树

时间复杂度: O（log2N）

缺点: 树的深度太大，磁盘读写频繁，效率低.

4. 哈希哈希方法（哈希表）

原理是首先根据键值和哈希函数创建一个哈希表（哈希表），然后根据键值通过哈希函数定位数据元素的位置.

数据结构: 哈希表

时间复杂度: 几乎为O（1），具体取决于发生了多少个冲突.

缺点: 哈希算法计算出的哈希值与原始键值不对应，因此只能执行等效过滤，不能进行基于范围的搜索，因此通常用于全文本索引.

要描述B树，首先将数据记录定义为二进制[key，data]，key是记录的键值，对于不同的数据记录，键互不相同； data是除键Data之外的数据记录. 那么B-Tree是一个满足以下条件的数据结构:

d是大于1的正整数，称为B树度.

h是一个正整数，称为B树的高度.

每个非叶子节点由n-1个键和n个指针组成，其中d <= n <= 2d.

每个叶节点至少包含一个键和两个指针，并且最多包含2d-1个键和2d指针. 叶节点指针全为空.

所有叶节点的深度相同，等于树的高度h.

键和指针彼此分开，节点的两端是指针.

节点中的键从左到右的顺序是不减小的.

所有节点都形成树形结构.

每个指针为空或指向另一个节点.

如果指针位于节点节点的左侧并且不为null，则指向该节点的所有键都小于v（key1），其中v（key1）是该节点的第一个键的值.

如果指针位于节点节点的最右边并且不为null，则指向该节点的所有键都大于v（keym），其中v（keym）是该节点的最后一个键的值

如果指针在节点节点的左右两侧是keyi和keyi + 1且不为null，则指向该节点的所有键均小于v（keyi + 1）且大于v（keyi）

由于B树的特性，通过B树中的键检索数据的算法非常直观: 首先从根节点执行二进制搜索，如果找到，则返回相应节点的数据，否则相应间隔的指针指向的节点递归搜索，直到找到该节点或找到空指针为止，前一个搜索成功，后一个搜索失败. B树上搜索算法的伪代码如下:

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
            if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

关于B树具有一系列有趣的属性，例如度为d的B树，如果其索引为N个键，则其树高h的上限为logd（（N + 1）/ 2）对于一个键，查找节点数的渐进复杂度为O（logdN）. 从这一点上我们可以看到B-Tree是一种非常有效的索引数据结构.

此外，由于插入和删除新数据记录会破坏B-Tree的性质，因此在插入和删除时，您需要在树上执行拆分，合并，转移和其他操作以保持B-Tree的性质. 树.

B树有许多变体，其中最常见的是B + Tree. 例如，MySQL通常使用B + Tree来实现其索引结构.

与B-Tree相比，B + Tree具有以下差异:

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

内部节点不存储数据，仅存储密钥；叶节点不存储指针.

在经典B + Tree的基础上优化了系统或文件系统中常用的B + Tree结构，并添加了顺序访问指针.

将指向相邻叶节点的指针添加到B + Tree的每个叶节点，以形成具有顺序访问指针的B + Tree. 此优化的目的是提高间隔访问的性能. 例如，如果要用上图中的键18到49查询所有数据记录，则当找到18时，只需要按照节点和指针的顺序进行一次访问即可，对所有数据节点的效率间隔查询被大大提及.

如上所述，磁盘I / O次数通常用于评估索引结构的优缺点. 通过对B树的分析，根据B树的定义，可以知道一次搜索最多需要访问h个节点. 为了实现此目标，还需要以下技术来实际实现B-Tree:

每次创建一个新节点时，直接申请一个页面空间，以确保一个节点也物理存储在页面中，再加上计算机存储分配是页面对齐的，我只需要实现一个节点/ O. 在B树中进行搜索最多需要h-1个I / O（根节点驻留内存），并且累进复杂度为O（h）= O（logdN）. 在一般实际应用中，输出d很大，通常超过100，因此h很小（通常不超过3）.

总而言之，使用B树作为索引结构的效率非常高.

对于红色和黑色的树，h显然要深得多. 由于逻辑上靠近的节点（父亲和儿子）可能在物理上距离较远并且无法利用局部性，因此红黑树的I / O渐进复杂度也为O（h），效率明显低于B-树.

如上所述，B + Tree更适合作为外部存储索引，其原因与内部节点d有关. 从上面的分析可以看出，d越大，索引性能越好，输出上限取决于节点中键和数据的大小:

dmax = floor（pagesize /（keysize + datasize + pointsize））

因为从B + Tree中的节点中删除了数据字段，它可以具有更大的输出和更好的性能.

#### 5. MyISAM和InnoDB的索引结构

MyISAM使用B + Tree作为索引结构，叶节点的数据字段存储数据记录的地址. 下图是MyISAM索引的原理图:

表中有三列. 假设我们使用Col1作为主键，则上图显示了MyISAM表的主索引. 可以看出，MyISAM索引文件仅保存数据记录的地址. 在MyISAM中，主索引和辅助索引（辅助密钥）之间在结构上没有区别，只是主索引要求密钥是唯一的，并且辅助索引的密钥可以重复. 如果我们在Col2上创建辅助索引，则该索引的结构如下图所示:

它也是B + Tree索引的结构，并且数据字段存储数据记录的地址. 因此，MyISAM中的索引检索算法是首先根据B + Tree搜索算法来搜索索引. 如果指定的键存在，则取出数据字段的值，然后以数据字段的值作为地址读取相应的数据记录. MyISAM索引方法也称为非聚集索引.

尽管InnoDB还使用B + Tree作为索引结构，但具体实现与MyISAM完全不同.

第一个主要区别是InnoDB的数据文件本身就是索引文件. 从上面可以看出，MyISAM索引文件和数据文件是分开的，并且索引文件仅保存数据记录的地址. 在InnoDB中，表数据文件本身是由B + Tree组织的索引结构，该树的叶节点数据字段包含完整的数据记录. 该索引的键是数据表的主键，因此InnoDB表数据文件本身就是主索引.

上图是InnoDB主索引（也是数据文件）的. 您可以看到叶节点包含完整的数据记录. 该索引称为聚簇索引. 因为InnoDB的数据文件本身必须通过主键聚合，所以InnoDB要求表必须具有主键（MyISAM可能没有主键）. 如果未明确指定，则MySQL系统将自动选择一个可以唯一地将数据记录标识为主键的列（如果不存在）. 对于这种类型的列，MySQL会自动为InnoDB表生成一个隐式字段，作为主键. 首要的关键. 该字段长6个字节，类型为long整数.

与MyISAM索引的第二个区别是InnoDB的辅助索引数据字段存储相应记录主键的值而不是地址. 换句话说，InnoDB的所有二级索引都将主键称为数据字段. 例如，下图显示了在Col3上定义的辅助索引:

此处使用英文字符的ASCII码作为比较标准. 聚集索引的实现使按主键进行的搜索非常高效，但是辅助索引搜索需要两次检索索引: 首先检索辅助索引以获取主键，然后使用主键来检索主记录中的记录. 主索引.

了解不同存储引擎的索引实现方法对于正确使用和优化索引非常有帮助. 例如，在了解了InnoDB的索引实现之后，很容易理解为什么不建议使用太长的字段作为主键，因为所有辅助索引都都引用主索引，并且太长的主索引会导致二级索引太大. 再举一个例子，在InnoDB中使用非单调字段作为主键不是一个好主意，因为InnoDB数据文件本身是B + Tree，并且非单调主键将导致数据文件保持特征. 插入新记录时B + Tree的出现频繁的拆分调整效率非常低，并且使用自增量字段作为主键是一个不错的选择.

#### 6. 使用索引的禁忌

由于索引可以加快查询的速度，因此只要查询语句需要索引，是否有必要构建索引？答案是否定的. 尽管索引加快了查询的速度，但索引有一个代价: 索引文件本身会占用存储空间，并且索引将增加插入，删除和修改记录的负担. 另外，MySQL还消耗资源以在运行时维护索引. 因此，索引越多越好. 通常，不建议在两种情况下建立索引.

表记录很少. 不建议创建索引. 例如，对于具有一千或两千甚至几百条记录的表，不需要构建索引. 让查询进行全表扫描. 至于多少记录就足够了，这个人有我自己的看法. 我的个人经验是基于2000年的分界线. 如果记录数不超过2000，则可以考虑不建立索引. 如果您有2000条以上的记录，则可以适当考虑索引.

不建议创建选择性低的索引. 所谓索引选择性（Selectivity）是指唯一索引值（也称为基数，基数）与表记录数（#T）之比:

索引选择性=基数/ #T

显然，选择性的范围是（0，1），选择性越高，索引值就越大，这取决于B + Tree的性质.

在使用InnoDB存储引擎时，如果没有特殊需要，请始终使用与业务无关的自动增量字段作为主键.

我经常看到讨论主键选择问题的帖子或博客. 有人建议使用业务增量主键. 有些人发现没有必要使用诸如学生ID或ID号之类的唯一字段作为主键. 无论支持哪种参数，大多数参数都在业务级别. 从索引优化的角度来看，使用InnoDB引擎而不是增加主键绝对不是一个好主意.

上面讨论了InnoDB的索引实现. InnoDB使用聚簇索引，数据记录本身存储在主索引（B + Tree）的叶节点上. 这就要求在同一叶子节点中的每个数据记录（一个内存页或磁盘页的大小）都以主键的顺序存储，因此，每当插入一条新记录时，MySQL就会根据它的主键和位置，如果页面达到负载因子（InnoDB默认为15/16），则会打开一个新页面（节点）.

如果表使用自动递增的主键，则每次插入新记录时，该记录将被顺序添加到当前索引节点的后续位置. 页面满时，将自动打开一个新页面. 如下图所示:

这将形成紧凑的索引结构，并以近似顺序填充. 因为不需要每次插入时都移动现有数据，所以它非常有效，并且在维护索引方面不会增加太多开销.

如果您使用非递增主键（例如ID号或学生号等），因为每次插入的主键的值都是近似随机的，因此必须将每个新记录插入到中间现有的索引页:

这时，MySQL必须移动数据以便将新记录插入适当的位置. 甚至目标页面也可能已写回到磁盘并从缓存中清除. 这时，必须从磁盘读回它，这增加了很多开销，并且频繁的移动和分页操作导致很多碎片，从而导致了紧凑的索引结构，然后不得不使用OPTIMIZE TABLE来重建表并优化填充页面.

样本索引规则

示例的导入>

show index from employees.titles;
-- 全列匹配
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';
EXPLAIN SELECT * FROM employees.titles WHERE title='Senior Engineer' AND from_date='1986-06-26' AND emp_no='10001';  
-- 最左前缀匹配
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001';
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer';
EXPLAIN SELECT * FROM employees.titles WHERE title='Senior Engineer' AND from_date='1986-06-26';
-- 查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26';
-- 使用in全值匹配 或者加辅助索引
EXPLAIN SELECT * FROM employees.titles
WHERE emp_no='10001'
AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager')
AND from_date='1986-06-26';
-- SHOW PROFILES;
-- 查询条件没有指定索引第一列。
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26';
-- 匹配某列的前缀字符串
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE '%Senior';
-- 范围查询
EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer';
EXPLAIN SELECT * FROM employees.titles
WHERE emp_no > '10001' and emp_no < '10010'
AND title='Senior Engineer'
AND from_date = '1986-01-01';
EXPLAIN SELECT * FROM employees.titles
WHERE emp_no BETWEEN '10001' and '10010'
AND title='Senior Engineer'
AND from_date = '1986-01-01';
-- 怎么建立联合索引
show index from employees.employees;
EXPLAIN SELECT * FROM employees.employees where emp_no = '10001';
EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido';
-- 前缀索引
SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;
SELECT count(DISTINCT(last_name))/count(*) AS Selectivity FROM employees.employees;
-- 基准
SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;
-- 选择性 0.7879
SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
-- 选择性 0.9007
SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
-- key_len的计算规则
-- 所有的索引字段，如果没有设置not null，则需要加一个字节。
-- 定长字段，int占四个字节、date占三个字节、char(n)占n个字符。
-- 对于变成字段varchar(n)，则有n个字符+两个字节。
-- 不同的字符集，一个字符占用的字节数不同。latin1编码的，一个字符占用一个字节，gbk编码的，一个字符占用两个字节，utf8编码的，一个字符占用三个字节。
-- key_len 22
ALTER TABLE employees.employees
ADD INDEX `first_name_last_name4` (first_name, last_name(4));
-- key_len 34
ALTER TABLE employees.employees
ADD INDEX `first_name_last_name5` (first_name, last_name);
ALTER TABLE employees drop index `first_name_last_name5`

参考:

〜galles / visualization / Algorithms.html

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-268608-1.html