很久之前（在一个遥远的银河系中。。。），开发者不得不完全地知道他们编码时所有的细节。他们对算法和数据结构必须要十分理解，因为他们接受不了浪费慢速计算机的CPU和内存的时间。
在这部分，我会提醒你一些概念，因为他们对理解数据库必不可少。我也会介绍数据库索引的概念。
现在，很多开发者不关系时间复杂度。。。 他们是对的！ 但当你处理茫茫大的数据时（我不是在说数千)，或者如果你再和毫秒在战斗时，理解这个这个概念即为重要。你知道吗，数据库是要处理以上两者情况！我不会耽误你很多时间，只是过个概念。这会帮助我们理解基于成本优化(Cost-Based Optimization) 的概念。
时间复杂度是用来观察算法在给定数量的数据的情况下会耗费多长时间。为了描述这个复杂度，计算机科学们使用数学的大O表示法。这个符号与一个函数一起使用，这个函数用于描述一个算法在给定数量的输入数据下需要执行多少次操作。
举个栗子，当我讲这算法在“O(some_function())”时，这意味着在一定数量的数据中，算法需要执行 some_funtion(a_certain_amount_of_data) 次操作。
更重要的不是数据量，而是当数量的量增大时操作次数增加的方式。而时间复杂的虽然没有给出准确的操作数，但是它依然是一个很好的想法。
在这图中，你可以看到不同类型的复杂度的走向。我用对数坐标去绘制的。换句话说，这些数据是从 1 到 10亿 的快速增长的。我们可以看到：
在数据量较少的时候，O(1) 和 O(n2) 的差异可以基本忽略不算。举个例子*1，假设你有一个算法，需要处理 2000 个元素
O(1) 和 O(n2) 看起来相差很多(4百万)，但是你最多失去的时候更多只有 2ms，知识一眨眼的时间。实际上，当前处理器可以处理每秒数亿次操作。这就是很多IT项目中性能和优化不是问题的原因。 正如我说的，面对十分庞大的数据时知晓时间复杂度这个概念还是非常重要的。如果这算法需要处理 1,000,000 个元素（这对数据库来讲也不是个很大的数据）
我不用算也知道 O(n2) 的算法可以让你有时间喝杯咖啡（甚至是第二杯），如果在数据量上再加多个0，就可以有时间小睡一下了。
再给你一些概念：
注意：在下一个部分，我们将看到这些算法和数据结构 有多种的复杂度类型：
时间复杂度通常使用最快的情况 我只会谈及时间复杂度，但是复杂度也能用于：
当然，还有比 n2 更可怕的时间复杂度，如：
注意：我没有给你大O符号的真正定义，只是个概念。你可以去维基百科阅读这篇文章关于大O的真正定义。
当你需要对一个集合进行排序的时候你要做什么?什么?你调用 sort() 函数 。。。 ok，好的答案。。。但是想了解数据库，你必须明白 sort() 函数是如何工作的。 有几个很好的排序算法，但是我将专注于最重要的一个：合并排序。你现在可能不明白为什么排序数据如何有用，也要在查询优化部分才去做。此外，明白合并排序将会帮助我们在之后理解一个普通数据库的操作叫合并关联(merge join)
像很多有用的算法一样，合并排序是基本一个技巧的：合并两个长度是 N/2 的已排序的数组到一个长度为 N 的数组中，只需要 N 次操作。这个操作叫合并。 我们用一个简单的例子来看看这是什么意思
从上面的图中可以看到，最想最终能构造出这长度为8的有序数组，你只需在那2个长度是4的有序数组中遍历一次。而由于那两个数组已经排序了，所以可以这样做：
1) 比较两个数组中的当前元素 (开始的时候，当前元素就是第一个元素了)
2) 把两个元素中数字最小的放到 最终数组(长度为8的） 中
3) 已被提取最小数字的数组访问下一个元素
4) 重复 1，2，3 直到有个数组访问到的最后一个元素
5) 然后你把另外一个数组的剩余的元素都放在最终数组中去。 这样做是可行的，因为两个长度是4的数组都是已排序的，因此你不需要从这些数组中来回进行访问。 现在我们已经理解了这个技巧，这是我的合并排序的伪代码。
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//递归调用
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);
//将两个有序的数组合并成一个大数组
array result := merge(new_left_array,new_right_array);
return result;合并排序将一个问题分解成较小的问题，然后找到较小问题的结果再去获取最初的问题的结果(注意：这种算法叫分而治之)。如果你不明白这种算法，不要害怕；我第一次看到它的时候也不名表。我对这类的算法会把它分成2个部分去看，这可能会帮助到你。
在切分的阶段，会用3个步将数组会被切分到单个元素的数组。正式步骤数应该是 log(N)(因为 N=8 ,log(N) = 3) 我怎样知道的？ 我是天才 一句话：数字。想一下，每个步骤都将初始数组的大小除以 2。步数是可以将初始数组除以2的次数。这是对数的精确定义(在以 2 为底的对数中)。
在排序阶段，你可以从单个元素开始排序。在每一步中，你可以执行多次的合并，总成本（每次合并的成本）是 N=8 次操作
因为有 log(N) 步，所以总共要 N*log(N) 个操作。
为什么这算法恐怖如斯? 因为：
注意：这种算法叫原地排序(我国亦有书称为内排序)
你可以对这算法进行修改，以便用磁盘空间来减少内容占用同时也不会有巨大的磁盘 I/O 损失。想法就是只对加载到内存的数据进行处理。这很重要，特别是当你的内存缓冲区仅有100MB而要对几GB的数据进行排序。 注意：这种算法叫外排序
你可以对这算法进行修改，可以让他在多线程/线程/服务器中使用
例如：分布式合并排序就是 Hadoop(大数据框架)的一个关键组件
这排序算法是绝大多数（可能不是所有）数据库会使用的，但不是为一种算法。 如果你想知道更多，你可以到看这篇论文，这论文说的数据库中常见排序算法的优缺点。
现在我们了解了时间复杂度和排序的概念，我也必须在告诉你3种数据结构。这挺重要的，因为他们也是现代数据库的支柱，我还会介绍数据库索引的概念。
二维数组是最简单的数据结构。表可以看作是一个数组。
例如：
这个二维数组是一个包含行和列的表：
虽然这很容易存储和可视化数据，但当你需要寻找一个特种的值时，它就显得很糟糕。
例如，如果你想找到所有在英国工作的人，你不得不查看每行看看这个人是不是属于英国的。这会耗费 n 个的操作（N 就是行数）这不算太差，但有更快的方式吗？这就轮到树的发挥了。
注意：大多数现代数据库会提供高级数组来高效存储表格，比如 堆组织表(heap-organized tables) 或者是索引组织表(index-organized tables)。但它不能改变在特定条件下 的按列进行快速搜索的问题。
二叉搜索树是具有特殊属性的二叉树，每个节点的键(key) 都必须是满足
下面让我们来看看二叉树可视化后是什么一回事
这棵树有 N=15 个元素。假设我要找键值为208的结点：
现在，假设我要找键值为40的结点
最后，这两次搜索都用了 树的层数 次，如果你仔细阅读了合并排序那部分，你应该会知道这是 log(N) 级别的时间复杂度。搜索的成本的 log(n),还不错
但这东西是挺抽象的，还是回到我们原来的问题吧。不用那些愚蠢的整数，想象下用字符串去表示上面那个表的人的国家。假设你有一个表有一个“国家(country)”的列(column):
这种搜索只花费你 log(N) 次操作，而如果直接用数组搜索就要用 O(N) 此操作了。你刚才想到的东西就是 数据库索引。 你可以为任何一组列(1个字符串，1个整数，2个字符串，1个整数和1个字符串，日期) 构建索引，只要你有一个函数去对比它们的键(keys)来建立键与键之间的顺序(数据库任何基本类型都能这样)
就像你看到那些，这里多了很多结点(之前的两倍以上)。其实，有额外的结点叫“决策结点”（decision nodes? 应该是蓝色的部分）这会帮你找到正确的结点（存储了相关表中的行的位置）。但搜索的复杂度仍然是 O(log(N)) (还是同一个级别)。差别最大的是最底部的叶子结点和后继结点都连在一起了。 使用这 B+ 树，如果在找 40 到 100 之间的所有值：
假设你找到了 M个后继结点而树有 N 个结点。这特征结点的搜索就像之前的树那些会耗费 log(N) 次操作。但一旦你找到这个结点了，你就能在 M 次操作内通过他们的连接知道 M 个后继结点了。这搜索只花费 M+log(N) 次操作，相对于之前的树要用 N 次操作。此外，你不用去读完整的树（只需读 M+log(N) 个结点），这意味着磁盘用得更少。如果 M 很少（比如是 200个）而 N 很大（有1,000,000行）两个算法就有很大的不同了。
但这也会带来新的问题，如果在数据库中添加或者修改一行(所以对应的B+树中去索引):
总之，B+树需要自排序和自平衡。值得庆幸的是，可以通过智能删除和智能插入的操作是实现。但这也带来一个成本，在B+中插入和删除都会是 log(N) 。这就是为何你会听到，使用太多索引不是好主意。其实，索引会减慢在表中插入/更新/删除行的速度，这是因为每条索引数据库都需要耗费 log(N) 的操作为进行更新维护。还有，添加索引意味着事务管理器有更多的负载(我们在文件的最后能看到这个管理器)
更多细节，你可以看维基百科的 B+树的B+树的文章。如果你想要在一个数据库中实现B+s树的例子你可以看这篇文章和这篇文章，这两篇文章都是 MySQL 的核心开发者写的。这两篇文章都关注 innoDB(MySQL引擎) 怎样处理索引
注意：读者告诉我，因为要底层化，所以 B+ 树需要完全平衡
我们最好一个重要的数据结果就是哈希表。这是非常有用的当你想快速寻找值。此外，明白哈希表会帮主我们再之后理解数据库一个基本连接操作叫哈希连接(hash join)。这数据结构也被数据库用来存储一些内部数据(像是锁表和缓冲池，我们会在后面的内容中看到这两个概念) 哈希表是能用键(key)快速寻找到元素的数据结构。要创建哈希表你需要定义：
这哈希表有10个桶。我很懒，所以只画了5个桶，但我知道你们很聪明，所有我让你想象其他5个桶。我使用的哈希函数是将键 模10(即key % 10)。换句话说，要找到桶我只要用元素的键(key)的最后一位数字
我使用的比较函数仅仅是2个整数间的是否相等。 假设你想元素78：
现在，假设你想获得元素59
如你所见，不同的值查找的成本的不一致的，这取决于你要找的值。 如果我现在讲哈希函数改成对键模 1,000,000 （即取最后6位），上面的第二次搜索也只花费1次操作，因为 000059 中没有元素。所以真正的挑战是寻找一个好的哈希函数来创建只包含很少元素的桶。 在我的例子中，找到一个好的哈希函数很容易。但那只是一个简单的例子，找一个好的哈希函数是很困难的，尤其是遇到(键)key是：
好的散列函数，会让哈希表搜索在 O(1)
为什么不用数组 恩，你问了个好的问题
更多的信息，你可以读我的文章，java HashMap 一个高效的哈希表的实现；在这篇文章中你不需要理解 java 的概念
原文：https://www.cnblogs.com/jojo-feed/p/10816212.html