6-2 MySQL 数据结构选择的合理性

6-2 MySQL 数据结构选择的合理性

@
目录

• 6-2 MySQL 数据结构选择的合理性
  
• 1. 全表查询
  
• 2. Hash 查询
  
• 3. 二叉搜索树
  
• 4. AVL 树
  
• 5. B-Tree
  
• 6.B + Tree
  
• 7. R树
  
• 8.  小结
  
• 附录：算法的时间复杂度
  
• 9. 最后：
  

这篇文章是我蹲在《尚硅谷》-康师傅博主家的 WiFi 上(不是)，连夜 Ctrl+C / V 俩的镇站神文。
这篇转载只是为了，跟大家分享好内容，没有任何商业用途。如果你喜欢这篇文章，请一定要去原作者 B站《尚硅谷-MySQL从菜鸟到大牛》看看，说不定还能发现更多宝藏内容呢！
从 MySQL 的角度来说，不得不考虑一个现实问题就是磁盘IO 。如果我们能让索引的数据结构尽量减少硬盘的 I/) 操作，所消耗的时间也就越小。可以说，磁盘的 I/O 操作次数 对索引的使用效率至关重要。
查找都是索引操作，一般来说索引非常大，尤其是关系型数据库，当数据量比较大的时候，索引的大小有可能几个G甚至更多，为了减少索引在内存的占用，数据库索引是存储在外部磁盘上的 。当我们利用索引查询的时候，不可能把整个索引全部加载到内存，只能逐一加载 ，那么MySQL 衡量查询效率的标准就是磁盘的 IO 次数。
1. 全表查询

全表查询较为简单，这里就在过多赘述了。
2. Hash 查询

加快查找速度的数据结构，常见的有两类：

• 树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是 O(log2N);
  
• 哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1); (key, value)
  

上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做 碰撞 ，在数据库中一般采用 链 接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示：

实验：体会数组和hash表的查找方面的效率区别
[code]// 算法复杂度为 O(n)@Testpublic void test1(){    int[] arr = new int[100000];    for(int i = 0;i < arr.length;i++){        arr = i + 1;    }    long start = System.currentTimeMillis();    for(int j = 1; j= 本节点，比我大的向右，比我小的向左</ul>2. 查找规则

为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量 降低树的高度 ，需要把 原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。
4. AVL 树

`每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5次 I/O 操作。虽然平衡二叉树的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。
针对同样的数据，如果我们把二叉树改成 M 叉树 （M>2）呢？当 M=3 时，同样的 31 个节点可以由下面 的三叉树来进行存储：

你能看到此时树的高度降低了，当数据量 N 大的时候，以及树的分叉树 M 大的时候，M叉树的高度会远小于二叉树的高度 (M > 2)。所以，我们需要把 `树从“瘦高” 变 “矮胖”。
5. B-Tree

B 树的英文是 Balance Tree，也就是 多路平衡查找树。简写为 B-Tree。它的高度远小于平衡二叉树的高度。
B 树的结构如下图所示：

一个 M 阶的 B 树（M>2）有以下的特性：
<ol>根节点的儿子数的范围是 [2,M]。
每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为 [ceil(M/2), M]。
叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key