Home > Database > Mysql Tutorial > 数据库索引及基本优化入门

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

WBOY
Release: 2016-06-07 17:40:24
Original
1063 people have browsed it

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

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

2013-7-26

 

一 前言

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

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

 

二.基础知识 2.1 页

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

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

 

2.2 B树

   B树即二叉搜索树,所有非叶子节点最低拥有两个子节点,基本信息如下图所示。都是小的元素放左边,大的元素放右边。比如说要查找某个元素,其时间复杂度就对应该元素的深度,如要查询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) 非叶子结点上的多个关键字是按照顺序排列的:K[1], K[2], …, K[M-1];且K[i] 

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

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

6) 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于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阶树的节点关键字数量应>3/2-1,

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

分裂后的效果如下图

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

 

2.3 B+树

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

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

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

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

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

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

 

 

三 索引存储

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

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template