浅谈数据库索引数据库索引有什么用( 二 ) _小知识

索引的原理：
想要理解索引原理必须清楚一种数据结构「平衡树」(非二叉)，也就是b tree或者 b+ tree 。当然，有的数据库也使用哈希桶作用索引的数据结构，主流的RDBMS都是把平衡树当做数据表默认的索引数据结构的。
在计算机科学中，B树是自平衡树数据结构。其保持数据排序，并允许在对数时间内完成搜索、顺序存取、插入和删除。B树是二叉搜索树的泛化，其节点可以具有多于两个的子节点。
与自平衡二叉搜索树不同的是，B树针对读取和写入大数据块的系统进行了优化。B树是外部存储器的数据结构的一个很好的例子。它通常用于数据库和文件系统。

文章插图
上图展示了一种可能的索引方式：
左边是数据表，一共有两列七条记录。
最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。
为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针。这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。

文章插图
三阶的 B Tree

B+的特性：
1.所有数据都存储在叶子结点的链表中，且链表中的数据都是有序存放的；
2.叶子节点间用指针相连。
3.不可能在非叶子结点命中；
4.非叶子结点相当于是叶子结点的索引，叶子结点相当于是存储数据的数据层；
5.更适合文件索引系统；
B+的性能：等于在数据集合做一次二分查找；

文章插图
二阶的 B+Tree
B+Tree与B Tree的区别：
B+树只有达到叶子结点才命中。
B-树可以在非叶子结点命中。
B+ 树是可变的 n 元树，通常每个节点具有大量子节点。
B+ 树由根，内部节点和叶组成。根可以是叶或具有两个或更多个子节点的节点。
B+ 树可以被视为B树，其中每个（内部）节点仅包含键（不是键值对），并在其底部附加一层链式的叶子节点。
B +树的主要价值在于存储数据，以便在面向块的存储上下文（特别是文件系统）中进行高效检索。
这主要是因为，与二叉搜索树不同的是，B +树具有非常高的扇出（节点中指向子节点的指针数，通常大约为100或更多），这减少了在树中查找元素所需的I / O操作数。
B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下，xfs文件系统比ext3/ext4效率高很多的原因之一就是，它的文件及目录索引结构全部采用B+树索引，而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构，因此在高I/O压力下，其IOPS能力不如xfs 。

PS：部分内容摘自互联网

二、数据库索引的作用为什么要创建索引呢？这是因为，创建索引可以大大提高系统的性能。
第一，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
第二，可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
第四，在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
第五，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。
也许会有人要问：增加索引有如此多的优点，为什么不对表中的每一个列创建一个索引呢？这种想法固然有其合理性，然而也有其片面性。
虽然，索引有许多优点，但是，为表中的每一个列都增加索引，是非常不明智的。
这是因为，增加索引也有许多不利的一个方面。
第一，创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
第二，索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
第三，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。
索引是建立在数据库表中的某些列的上面。
因此，在创建索引的时候，应该仔细考虑在哪些列上可以创建索引，在哪些列上不能创建索引。

浅谈数据库索引 数据库索引有什么用( 二 )

浅谈数据库索引数据库索引有什么用( 二 )