网站建设方案哪家好 推荐,广州天河区网站设计公司,效果好企业营销型网站建设开发,成都私人放款联系方式电话索引
引入
我们知道#xff0c;数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快#xff0c;因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找#xff08;linear search#xff09;#xff0c;这种复杂度为…索引
引入
我们知道数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找linear search这种复杂度为O(n)的算法在数据量很大时显然是糟糕的好在计算机科学的发展提供了很多更优秀的查找算法例如二分查找binary search、二叉树查找binary tree search等。如果稍微分析一下会发现每种查找算法都只能应用于特定的数据结构之上例如二分查找要求被检索数据有序而二叉树查找只能应用于二叉查找树上但是数据本身的组织结构不可能完全满足各种数据结构例如理论上不可能同时将两列都按顺序进行组织所以在数据之外数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用指向数据这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。
简介
目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种BTree(B树)作为索引结构。BTree是数据库系统实现索引的首选数据结构。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。
索引数据结构
了解索引就需要从索引常见的数据结构开始了解学习这是几种常见的的索引数据结构
二叉树
二叉树是每个节点最多只有两个分支即不存在分支度大于2的节点的树结构。通常被称之为“左子树”和“右子树” 二叉树示例图
左子树父节点右子树
二叉树的第i层至多有有2^(i-1)个节点
深度为K的二叉树至多总共有个2^k-1节点定义根节点所在深度 k00而总计拥有节点数符合的称为“满二叉树”
二叉树通常作为数据结构应用典型用法是对节点定义一个标记函数将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆并应用于高效率的搜索和排序。
同时学习数据结构这里还推荐Data Structure Visualizations进行学习可以非常直观的看到数据结构允许的过程一步一步的怎么走的都可以很清晰看得到。
找到其中的Binary Search Trees二叉树
可以看到二叉树不适合用作当作索引的数据量庞大的话或者按顺序插入 二叉树的层数会很大查找效率固然也很慢了
红黑树Red-Black Trees
是一种自平衡二叉查找树典型用途是实现关联数组。
红黑树的结构复杂但它的操作有着良好的最坏情况运行时间并且在实践中高效它可以在O(log n)时间内完成查找插入和删除这里的n是树中元素的数目。
红黑树遵行以下原则
节点是红色或黑色。
根是黑色。
所有叶子都是黑色叶子是NIL节点。
每个红色节点必须有两个黑色的子节点。从每个叶子到根的所有路径上不能有两个连续的红色节点。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。下面是一个具体的红黑树的图例 这些约束确保了红黑树的关键特性从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例这个在高度上的理论上限允许红黑树在最坏情况下都是高效的而不同于普通的二叉查找树。
要知道为什么这些性质确保了这个结果注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点这就表明了没有路径能多于任何其他路径的两倍长。
同样红黑树也不适用于MySQL的索引数据量庞大之后数层也会变大。
推荐阅读
小灰红黑树
其他数据结构
由于无法装入内存则必然依赖磁盘或SSD存储。而内存的读写速度是磁盘的成千上万倍与具体实现有关因此核心问题是“如何减少磁盘读写次数”。
首先不考虑页表机制假设每次读、写都直接穿透到磁盘那么
线性结构读/写平均O(n)次二叉搜索树BST读/写平均O(log2(n))次如果树不平衡则最差读/写O(n)次自平衡二叉搜索树AVL在BST的基础上加入了自平衡算法读/写最大O(log2(n))次红黑树RBT另一种自平衡的查找树读/写最大O(log2(n))次
BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n))其中AVL和RBT都比BST多了自平衡的功能将读写次数降到最大O(log2(n))。
假设使用自增主键则主键本身是有序的树结构的读写次数能够优化到树高树高越低读写次数越少自平衡保证了树结构的稳定。如果想进一步优化可以引入B树和B树。
B树B-Trees
又称多路平衡查找树。大多数存储引擎都支持B树索引。b树通常意味着所有的值都是按顺序存储的并且每一个叶子节点到根的距离相同。B树索引能够加快访问数据的速度因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的B树。
在B树中内部非叶子节点可以拥有可变数量的子节点数量范围预先定义好。当数据被插入或从一个节点中移除它的子节点数量发生变化。为了维持在预先设定的数量范围内内部节点可能会被合并或者分离。
如下图所示
叶节点具有相同的深度叶节点的指针为空所有索引元素不重复节点中的数据索引从左到右递增排列无论中间节点还是叶子节点都带有卫星数据data索引元素所指向的数据记录
只演示了插入的过程其中可以通过delete、find执行删除和查找操作。直观的感受到B树的执行过程。
每个节点存储了多个Key和子树子树与Key按顺序排列。
同二叉搜索树类似每个节点存储了多个key和子树子树与key按顺序排列。页表的目录是扩展外存加速磁盘读写一个页Page通常4K等于磁盘数据块block的大小见inode与block的分析操作系统每次以页为单位将内容从磁盘加载到内存以摊分寻道成本修改页后再择期将该页写回磁盘。考虑到页表的良好性质可以使每个节点的大小约等于一个页使m非常大这每次加载的一个页就能完整覆盖一个节点以便选择下一层子树对子树同理。对于页表来说AVL或RBT相当于1个key2个子树的B树由于逻辑上相邻的节点物理上通常不相邻因此读入一个4k页页面内绝大部分空间都将是无效数据。假设key、子树节点指针均占用4B则B树节点最大m * (4 4) 8m B页面大小4KB。则m 4 * 1024 / 8m 512一个512叉的B树1000w的数据深度最大 log(512/2)(10^7) 3.02 ~ 4。对比二叉树如AVL的深度为log(2)(10^7) 23.25 ~ 24相差了5倍以上。震惊B树索引深度竟然如此
那为什么B数这么厉害了还有B树的出现呢必然是解决B树存在的问题
1、为定位行数
2、无法处理范围查询
问题1为定位行数
数据表的记录有多个字段仅仅定位到主键是不够的还需要定位到数据行。有3个方案解决
直接将key对应的数据行可能对应多行存储子节点中。
数据行单独存储节点中增加一个字段定位key对应数据行的位置。
修改key与子树的判断逻辑使子树大于等于上一key小于下一key最终所有访问都将落于叶子节点叶子节点中直接存储数据行或数据行的位置。方案1直接pass存储数据行将减少页面中的子树个数m减小树高增大。
方案2的节点中增加了一个字段假设是4B的指针则新的m 4 * 1024 / 12m 341.33 ~ 341深度最大 log(341/2)(10^7) 3.14 ~ 4。
方案3的节点m与深度不变但时间复杂度变为稳定的O(logm(n))。
方案3可以考虑。
问题2无法处理范围查询
实际业务中范围查询的频率非常高B树只能定位到一个索引位置可能对应多行很难处理范围查询。改动较小的是2个方案
不改动查询的时候先查到左界再查到右界然后DFS或BFS遍历左界、右界之间的节点。
在“问题1-方案3”的基础上由于所有数据行都存储在叶子节点B树的叶子节点本身也是有序的可以增加一个指针指向当前叶子节点按主键顺序的下一叶子节点查询时先查到左界再查到右界然后从左界到有界线性遍历。乍一看感觉方案1比方案2好——时间复杂度和常数项都一样方案1还不需要改动。但是别忘了局部性原理不管节点中存储的是数据行还是数据行位置方案2的好处在于依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。
推荐阅读 小灰B树
B树
主要变动如上所述
修改key与子树的组织逻辑将索引访问都落到叶子节点
按顺序将叶子节点串起来方便范围查询回顾上一个B树一个m阶的B树具有如下几个特征
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子其中 m/2 k m
3.每一个叶子节点都包含k-1个元素其中 m/2 k m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
一个m阶的B树具有如下几个特征
1.有k个子树的中间节点包含有k个元素B树中是k-1个元素每个元素不保存数据只用来索引所有数据都保存在叶子节点。
2.所有的叶子结点包含了全部元素的信息及指向含这些元素记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点在子节点元素中是最大或最小元素。
B树特性总结
B树是B树的升级版其有如下特性
非叶子节点不存储data只存储索引(冗余)可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接提高区间访问的性能
只有叶子节点带有卫星数据data索引元素所指向的数据记录在动图中可以看出B树的每一个叶子节点都有一个指针指向下一个节点把所有的叶子节点串在一起。索引数据都存储在叶子节点中。
B树相比于B树有什么优势呢
1.单一节点存储更多的元素使得查询的IO次数更少。
2.所有查询都要查找到叶子节点查询性能稳定。
3.所有叶子节点形成有序链表便于范围查询。
总结B树相比B树的优势有三1.IO次数更少2.查询性能稳定3.范围查询简便。
推荐阅读
程序员小灰-B树
Hash索引
hash索引基于hash表实现Hash 索引是将索引键通过 Hash 运算之后将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中。只有精准匹配索引所有列的查询才有效。索引的检索可以一次定位不像B-Tree索引需要从根节点出发到目标节点。虽然Hash索引很快远高于B-tree索引但是也有其弊端。
Hash索引仅仅能满足,IN,查询也就是等值查询不能使用范围查询。很受限由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值所以它只能用于等值的过滤不能用于基于范围的过滤因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系并不能保证和Hash运算前完全一样。
由于Hash索引是通过hash表实现其本身是没有排序的。由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样所以数据库无法利用索引的数据来避免任何排序运算
Hash索引不能利用部分索引键查询对于组合索引Hash索引在计算hash值的时候是组合索引键合并后再一起计算hash值而不是单独计算hash值所以通过组合索引的前面一个或几个索引键进行查询的时候Hash 索引也无法被利用。
Hash 索引在任何时候都不能避免表扫描前面已经知道Hash 索引是将索引键通过 Hash 运算之后将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中由于不同索引键存在相同 Hash 值所以即使取满足某个 Hash 键值的数据的记录条数也无法从 Hash 索引中直接完成查询还是要通过访问表中的实际数据进行相应的比较并得到相应的结果。
Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。对于选择性比较低的索引键如果创建 Hash 索引那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦会浪费多次表数据的访问而造成整体性能低下。MyISAM索引实现MyISAM引擎使用BTree作为索引结构,叶节点的data域存放的是数据记录的地址
