《关系型数据库工作原理》读后感

做为一名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日志

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

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

发表新评论