当前位置:  首页  >  PHP教程  >  PHP 进阶  >  网络编程

数据库索引及基本优化入门

数据库索引及基本优化入门2013-7-26一前言经常在面试中发现很多人工作了好多年了,项目经验也不少,用过各种数据库,但大都不知道这些SQL语句背后的基本原理,更别说数据库优化了。平时做项目只知道实现功能,懒得学习,懒得思考,懒得看书(其实本人也

数据库索引及基本优化入门 2013-7-26 一前言 经常在 面试中发现很多人工作了好多年了,项目经验也不少,用过各种数据库,但大都不知道这些SQL语句背后的基本原理,更别说数据库优化了。平时做项目只知道实现功能,懒得学习,懒得思考,懒得看书(其实本人也

数据库索引及基本优化入门

2013-7-26

一 前言

经常在面试中发现很多人工作了好多年了,项目经验也不少,用过各种数据库,但大都不知道这些SQL语句背后的基本原理,更别说数据库优化了。平时做项目只知道实现功能,懒得学习,懒得思考,懒得看书(其实本人也是,不要找借口说这是China国情,项目是给boss做的,但技术和成长是你自己的)。

本篇文章主要讲述数据库索引的基本原,及基本的数据库优化的知识。所有知识均为本人自己学习的总结以及网络。此篇文章主要是为公司内部人员培训所用的,整理出来只是希望和大家分享、交流,因本人技术有限,若有遗漏、错误,希望多多指正、交流。

二.基础知识 2.1 页

数据库文件存储是已页为存储单元的,一个页是8K(8192Byte),一个页就可?#28304;?#25918;N行数据。我们常用的页类型就是数据页和索引页。一个页中除了存放基本数据之外还需要存放一些其他的数据,如页的信息、偏移量等,如下图所示。

虽然SQLServer是以页为单位存储数据,但是其分配空间是以一个盘区为单位的(8个页=64K),这样做的目的主要是为提高I/O的性能。

2.2 B树

B树即二叉搜索树,所有非叶子节点最低拥有两个子节点,基本信息如下图所示。都是小的元素放左边,大的元素放右边。比如说要查找某个元素,其时间复杂度就?#26434;?#35813;元素的深度,如要查询9,从根节点开始,只要比较三次就找到他了,其查询效率是非常高的。

子节点:最多两个子节点(指针分别指向Left和Right)

阶数(节点子节点个数):2

深度:就是层数,各个叶子节点不一定一样,如节点21的深度为4,40的深度为3

2.2 B-树

B-树是一中多路搜索树,其阶数可以自定义(>2),是很多数据及文件系统应用的一种索引结构,基本特征如:

1) 阶数(M)>2,即孩子数量大于2个

2) 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

3) 非叶子结点上的多个关键字?#21069;?#29031;顺序排列的:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

4) 所有叶子节点都位于同一层,因此叶子节点的深度都是一样的

5) 非叶子结点的关键字个数=指向儿子的指针个数-1;

6) 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键?#20013;?#20110;K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

如下图是一个三阶的B-树,节点[18]有两个指针分别指向其2个子节点。

这时如果要插入一个值17,其处理步骤:

1) 从根节点进入,17小于22,进入左边的节点[18];

2) [18]不是叶子节点,继续向下搜索,17小于18,进入其左边的子节点[12,16];

3) [12,16]为叶子节点,插入到该节点;

4) 节点[12,16,17]元素大于2了(3?#36164;?#30340;节点关键字数量应>3/2-1,<3-1),因此该节点需要分裂,分裂中间的元素16到父节点18中去;

5) 12,17分裂成了两个子节点了;

分裂后的效果如下图

以上图片效果来自一个外国大学里面的的在线版B-树的测试,网站:~galles/visualization/BTree.html ,大家可以去这个网站测试,效果很直观,外国人就是牛。本人以前用C#+GDI实现过类似的效果,结果还是可以的,就是当树太大的时候,布局不好处理了。

2.3 B+树

B+树是B-树的变体,也是一种多路搜索树,一棵m 阶的B+树和m 阶的B-树的差异在于:

l 非叶子节点的子节点和其关键字相同,即节点有三个元素(关键字),他就肯定有三个子节点;

l 非叶子节点的子节点P[i],指向关键?#31181;?#23646;于[K[i], K[i+1])的子树(B-树是开区间);

l 所有叶子节点增加一个链指针;

l 所有关键字的数据都在叶子节点中;

如下图所示,图片来自网络()。

三 索引存储

B+树和B-树是数据库广发应用的索引存储结构,它可以极大的提高数据查找的效率。关于B-树、B+树的原理与应用的详细可以参考文档:

吐了个 "CAO" !
扫码关注 PHP1 官方微信号
PHP1.CN | 中国最专业的PHP中文社区 | PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | PHP问答
Copyright ? 1998 - 2020 PHP1.CN. All Rights Reserved PHP1.CN 第一PHP社区 版权所有
     
28玩法
14场进球彩预测 福建11选5遗漏top 彩票开奖25选72月12 炸金花网络游戏 一分赛车计划 彩客网胜平负 高频彩票调整实体店 极速11选5 北单足球奖金计算 竞彩足球历史数据统计 pt招财进宝试玩 亚洲必赢官方网 传奇彩票 环亚ag平台官方入口 扑克大老2怎么玩