做为一名phper，经常都在使用MySQL数据库，但数据库是如何工作的，确是毫不知情。近期通过朋友分享的一篇文章《关系型数据库工作原理》简单了解了一些关于数据库的算法、数据结构的理论知识。

通过阅读该文简单归结了以下几个要点：

1.时间复杂度 T(n)=O(f(n)) FYI:http://www.jianshu.com/p/99bac69fdd97

* 时间复杂度定义: 算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

2.归并排序

中心思想：把一个问题分解为小问题，解决了多个小问题就解决了整个问题（这种算法统称为分治算法）

第1阶段：分解，把一个大数组分解为多个小数组，分解次数 log(n) 次

第2阶段：排序，几个小数组【按顺序】合并起来，构成大数组

3.现代数据库3种数据结构：数组、二叉树、哈希表

* 二维数组：能搞定数据的存储和抽象，但是要查询某个特定数据时需要逐行遍历查找，时间复杂度O(n)。

* 二叉数：

构成：每个节点左边的所有节点都比这个节点小，每个节点右边的所有节点都比这个节点大。

查询：二叉树查询次数，取决于树的深度log(n)，所以这个查询的时间复杂度是O(log(n))。

B+树：只在最末端的节点（叶子节点）才存储数据，其它节点只有路由功能（查询功能）。

* 哈希表：是一种通过元素的key快速查询到元素的数据结构。

要点：

1)定义各元素的key（通过一种方法从元素中提取出关键码）

2)定义一个哈希函数，可以通过key计算出元素所在位置(位置称为bucket)

3)定义一个“key比较函数”：实现各个key的比较，如果找到了某个元素所在bucket，还要通过这个函数在bucket内的众多元素中找到这个元素。

4.索引：索引是已经排好序了

5.查询管理器

* 查询解析：

1)这个表是否存在，列是否存在

2)对列的不同类型运算是否有效（比如，不能拿一个数字和一个字符串进行对比运算，不能对一个数字执行substring()函数）

3)检查用户是否有权限读或者写这个表（DBA账户设定）

解析过程，sql语句会被转换为一种内部表示方式（通常是一种数结构），如果通过了“查询解析”的检查，那么这个内部表示方式会被传递到“查询重写”

* 查询重写

* 统计

* 查询优化

6.log日志

文章中还有许多点，如缓存、事务管理等，以上仅列举了本人目前较为关注到的部分。

在开发中数据库是必不可少的一环，很多功能的效率或问题往往出在数据库的使用上。增加对数据库的理解，有利于合理使用数据库或做出一定程度的优化。