Mysql索引数据结构-创新互联

Mysql索引数据结构(来源)##

索引常见数据结构：

1. 顺序查找: 最基本的查询算法-复杂度O（n），大数据量此算法效率糟糕。

2. 二叉树查找（binary tree search）: O(log2n)，数据本身的组织结构不可能完全满足各种数据结构。

3. hash索引 无法满足范围查找。哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。

4. 二叉树、红黑树 [复杂度O(h)]导致树高度非常高(平衡二叉树一个节点只能有左子树和右子树),逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，IO次数多查找慢,效率低。todo 逻辑上相邻节点没法直接通过顺序指针关联，可能需要迭代回到上层节点重复向下遍历找到对应节点，效率低

5. B-Tree

   • B-TREE 每个节点都是一个二元数组: [key, data]，所有节点都可以存储数据。key为索引key,data为除key之外的数据。
   • 检索原理：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或未找到节点返回null指针。
   • 缺点：1.插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。造成IO操作频繁。2.区间查找可能需要返回上层节点重复遍历，IO操作繁琐。

6. B+Tree: B-Tree的变种

   • 与B-Tree相比，B+Tree有以下不同点：非叶子节点不存储data，只存储索引key；只有叶子节点才存储data
   • Mysql中B+Tree：在经典B+Tree的基础上进行了优化，增加了顺序访问指针。在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。这样就提高了区间访问性能

为什么Mysql选择B+TREE索引? B+TREE索引有什么好处?
索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数，提升索引效率。

局部性原理与磁盘预读:
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。预读可以提高I/O效率。预读的长度一般为页（page:计算机管理存储器的逻辑块-通常为4k）的整倍数. 主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中。

B-/+Tree索引的性能优势：
一般使用磁盘I/O次数评价索引优劣。1.结合操作系统存储结构优化处理： mysql巧妙运用操作系统存储结构(一个节点分配到一个存储页中->尽量减少IO次数) & 磁盘预读(缓存预读->加速预读马上要用到的数据).2.B+Tree 单个节点能放多个子节点，相同IO次数，检索出更多信息。3.B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

来源
B+树的优势:
因为B+树没有与内部节点相关联的数据，所以在内存页面上可以容纳更多的键。因此，访问叶子节点上的数据需要更少的缓存丢失。
B+树的叶节点是链接的，因此对树中的所有对象进行全面扫描只需要一个线性遍历所有叶节点。另一方面，B树需要遍历树中的每一层。这种全树遍历可能比B+叶子的线性遍历涉及更多的缓存丢失。
B树的优势:
因为B树包含每个键的数据，所以经常访问的节点可以更靠近根，因此可以更快地访问。