数据库

SQL

1、SQL对大小写不敏感

2、可以把 SQL 分为两个部分：数据操作语言 (DML) 和数据定义语言 (DDL)。SQL (结构化查询语言)是用于执行查询的语法。
2.1 SQL 语言也包含用于更新、插入和删除记录的语法。
查询和更新指令构成了 SQL 的 DML 部分：
select - 从数据库表中获取数据
update - 更新数据库表中的数据
delete - 从数据库表中删除数据
insert into - 向数据库表中插入数据

2.2 SQL 的数据定义语言 (DDL) 部分使我们有能力创建或删除表格。我们也可以定义索引（键），规定表之间的链接，以及施加表间的约束。
SQL 中最重要的 DDL 语句:
create database <数据库名> - 创建新数据库
alter database <数据库名> - 修改数据库
create table <数据库名> - 创建新表
alter table <数据库名> - 变更（改变）数据库表
drop table <数据库名> - 删除表
create index <数据库名> - 创建索引（搜索键）
drop index <数据库名> - 删除索引

3、常用SQL语句
3.1 查看现有数据库/表 show database/tables;
3.2 连接数据库 use <数据库名>;
3.3 从.sql文件引入SQL语句 source <.sql文件路径>; 3.4 删除数据库 drop database <数据库名>; 3.5 使用如下语句查看表中的列的基本信息：describe <表名>;


9. 在表中插入新纪录
INSERT INTO <表名> (<列名1>, <列名2>, <列名3>, …)
VALUES (<值1>, <值2>, <值3>, …);

10. 在表中更新记录
UPDATE <表名>
SET <列名1> = <值1>, <列名2> = <值2>, ...
WHERE <条件>;

SELECT语句可以从表中选择数据：
SELECT <列名1>, <列名2>, …
FROM <表名>;

数据库索引
 索引是对数据库表中一个或多个列的值进行排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B-TREE及其变种。因为索引存储引擎不会再去扫描整张表，根节点保存了子节点的指针，因此存储引擎从根节点开始，根据指针快速寻找数据，加速了数据访问
1). 索引的底层实现原理和优化
在数据结构中，最常见的搜索结构就是二叉搜索树和AVL树(高度平衡的二叉搜索树，为了提高二叉搜索树的效率，减少树的平均搜索长度)。然而，无论二叉搜索树还是AVL树，当数据量比较大时，都会由于树的深度过大而造成I/O读写过于频繁，进而导致查询效率低下，因此对于索引而言，多叉树结构成为不二选择。特别地，B-Tree的各种操作能使B树保持较低的高度，从而保证高效的查找效率。
2). 索引的优点
1、加快数据的检索速度，这也是创建索引的最主要的原因；
2、表和表之间的连接；
3、用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间；
4、创建唯一性索引，可以保证数据库表中每一行数据的唯一性；
3). 什么样的字段适合创建索引？
1、作查询选择的字段
2、作表连接的字段
3、出现在order by, group by, distinct 后面的字段
4). 创建索引时需要注意什么？
1、字段：应该指定列为NOT NULL，除非你想存储NULL。在mysql中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。你应该用0、一个特殊的值或者一个空串代替空值；
2、离散大的字段：（变量各个取值之间的差异程度）的列放到联合索引的前面，可以通过count()函数查看字段的差异值，返回值越大说明字段的唯一值越多，字段的离散程度高；
3、字段越小越好：数据库的数据存储以页为单位，一页存储的数据越多，一次I/O操作获取的数据越大效率越高。
5). 索引的缺点
1、时间方面：创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度；
2、空间方面：索引需要占物理空间。
6). 索引的分类
1、普通索引和唯一性索引：索引列的值的唯一性
2、单个索引和复合索引：索引列所包含的列数
3、聚簇索引与非聚簇索引：聚簇索引按照数据的物理存储进行划分的。
对于一堆记录来说，使用聚集索引就是对这堆记录进行堆划分，即主要描述的是物理上的存储。正是因为这种划分方法，导致聚簇索引必须是唯一的。聚集索引可以帮助把很大的范围，迅速减小范围。但是查找该记录，就要从这个小范围中Scan了；而非聚集索引是把一个很大的范围，转换成一个小的地图，然后你需要在这个小地图中找你要寻找的信息的位置，最后通过这个位置，再去找你所需要的记录。
7). 主键、自增主键、主键索引与唯一索引概念区别
1、主键：指字段唯一、不为空值的列；
2、主键索引：指的就是主键，主键是索引的一种，是唯一索引的特殊类型。创建主键的时候，数据库默认会为主键创建一个唯一索引；
3、自增主键：字段类型为数字、自增、并且是主键；
4、唯一索引：索引列的值必须唯一，但允许有空值。
主键是唯一索引，这样说没错；但反过来说，唯一索引也是主键就错误了，因为唯一索引允许空值，主键不允许有空值，所以不能说唯一索引也是主键。
8). 主键就是聚集索引吗？主键和索引有什么区别？
主键是一种特殊的唯一性索引，其可以是聚集索引，也可以是非聚集索引。在SQLServer中，主键的创建必须依赖于索引，默认创建的是聚集索引，但也可以显式指定为非聚集索引。InnoDB作为MySQL存储引擎时，默认按照主键进行聚集，如果没有定义主键，InnoDB会试着使用唯一的非空索引来代替。如果没有这种索引，InnoDB就会定义隐藏的主键然后在上面进行聚集。所以，对于聚集索引来说，你创建主键的时候，自动就创建了主键的聚集索引。
MySQL如何查看索引情况并优化
**索引类型：**mysql中支持 hash索引 和 btree索引 。innodb和myisam只支持 btree索引，而memory和heap存储引擎可以支持hash和btree索引
**查询索引方式：**我们可以通过 show status like '%Handler_read%'; 语句查询当前索引使用情况
结论：
1）如果索引正在工作，则Handler_read_key的值会很高，这个值代表一个行被索引值读的次数，很低值表名增加索引得到的性能改善不高，因此索引并不经常使用
2）如果Handler_read_rnd_next值很高意味着查询运行效率很低，应该建立索引补救，这个值含义是在数据文件中读取下一行的请求数。如果正在进行大量表扫描，Handler_read_rnd_next的数值将会很高。说明索引不正确或者没有利用索引。

优化：
1）优化insert语句：
1.尽量采用 insert into test values(),(),(),()…
2.如果从不同客户插入多行，能通过使用insert delayed语句得到更高的速度，delayed含义是让insert语句马上执行，其实数据都被放在内存队列中个，并没有真正写入磁盘，这比每条语句分别插入快的多；low_priority刚好相反，在所有其他用户对表的读写完后才进行插入。
3.将索引文件和数据文件分在不同磁盘上存放（利用建表语句）
4.如果进行批量插入，可以增加bulk_insert_buffer_size变量值方法来提高速度，但是只对MyISAM表使用
5.当从一个文本文件装载一个表时，使用load data file，通常比使用insert快20倍
 2）优化group by语句：
 默认情况下，mysql会对所有group by字段进行排序，这与order by类似。如果查询包括group by但用户想要避免排序结果的消耗，则可以指定order by null禁止排序。
 3）优化order by语句：
 某些情况下，mysql可以使用一个索引满足order by字句，因而不需要额外的排序。where条件和order by使用相同的索引，并且order by的顺序和索引的顺序相同，并且order by的字段都是升序或者降序。
 4）优化嵌套查询：
 mysql4.1开始支持子查询，但是某些情况下，子查询可以被更有效率的join替代，尤其是join的被动表待带有索引的时候，原因是mysql不需要再内存中创建临时表来完成这个逻辑上需要两个步骤的查询工作。
数据结构
栈和堆的区别

堆和栈的概念存在于数据结构中和操作系统内存中。 
在数据结构中，栈中数据的存取方式为先进后出。而堆是一个优先队列，是按优先级来进行排序的，优先级可以按照大小来规定。完全二叉树是堆的一种实现方式。 
在操作系统中，内存被分为栈区和堆区。栈区内存由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。堆区内存一般由程序员分配释放，若程序员不释放，程序结束时可能由垃圾回收机制回收。

树的深度优先遍历和广度优先遍历分别用了什么数据结构
树的存储可以分为顺序存储和链式存储结构，但为了满足多子树的场景，树的存储方式利用了顺序存储和链式存储的，其方法有双亲表示法、孩子表示法、孩子兄弟表示法。
1、广度优先遍历/宽度优先搜索(https://www.zhihu.com/question/28549888)

英文缩写为BFS，即Breadth First Search。 
我们每一次搜索到一个点的时候，如果这个点不符合条件，那么搜索同一层中符合条件的点，再把这一层中符合要求的点一一拓展，按照上述形式搜索下去。 
其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。 
先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。 
广度优先遍历树，需要用到队列（Queue）来存储节点对象,队列的特点就是先进先出
2、深度优先搜索

英文缩写为DFS，即Depth First Search。 
我们每一次搜索到一个点的时候，如果这个点不符合条件，那么就return，返回到上一层（就是常说的回朔），如果这个点符合条件，就一直搜索下去，直到没有点可以搜索。 
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。 
深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。
平衡二叉树 AVL
任一节点对应的两棵子树的最大高度差为1，也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)
数组和链表的区别
数组的特点
1）在内存中，数组是一块连续的区域。 拿上面的看电影来说，这几个人在电影院必须坐在一起。
2）数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。 比如看电影时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。
3）插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。 当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。
4）随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
5）并且不利于扩展，数组定义的空间不够时要重新定义数组。
链表的特点
1）在内存中可以存在任何地方，不要求连续。 在电影院几个人可以随便坐。
2）每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……
3）增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
3）查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起。
4）不指定大小，扩展方便。链表大小不用定义，数据随意增删。
各自的优缺点
1）数组的优点：随机访问性强；查找速度快
2）数组的缺点：插入和删除效率低；可能浪费内存；内存空间要求高，必须有足够的连续内存空间；数组大小固定，不能动态拓展
 1）链表的优点：插入删除速度快；内存利用率高，不会浪费内存；大小没有固定，拓展很灵活。
 2）链表的缺点；不能随机查找，必须从第一个开始遍历，查找效率低



-
数组
链表


读取
O(1)
O(n)

插入
O(n)
O(1)

删除
O(n)
O(1)
动态数组
数组按照操作分为增删改查
增
1）addLast(e)：添加的元素是在数组尾部操作，不需要移动其他元素位置，直接添加即可。时间复杂度为O(1)。
2）addFirst(e)：添加的元素是在头部操作，插入时其他元素要依次往后挪。时间复杂度为O(n)。
3）add(index,e)：根据索引添加元素，我们并不知道索引具体会插入在哪个位置。根据概率论分析，时间复杂度O(n/2) = O(n)。
4）除此之外我们还要考虑resize,当数组进行扩容时，时间复杂度同样为O(n)。
删
1） removeLast(e)：同增加操作一样，时间复杂度为O(1)。
2）removeFirst(e)：同增加操作一样，时间复杂度为O(n)。
3）remove(index,e)：同增加操作一样，时间复杂度O(n/2) = O(n)。
4） 一样也要考虑到扩容，时间复杂度为O(n)。
改
set(index,e)：根据索引修改元素。当知道索引时，可以直接修改元素而不需要对其他元素进行操作。故时间复杂度O(1)。
查
1）get(index)：通过索引查询元素，直接查找。时间复杂度O(1)。
2）contains(e)：查看数组中是否包含该元素。由于不是通过索引查找，我们需要遍历数组，增加了时间量。时间复杂度O(n)。
3）find(e)：查看数组中对应的索引是多少。同contains一样需要遍历数组。时间复杂度O(n)。

电子开发网

数据库与数据结构_数据库数据结构

数据库

SQL

数据库索引

MySQL如何查看索引情况并优化

数据结构

栈和堆的区别

树的深度优先遍历和广度优先遍历分别用了什么数据结构

平衡二叉树 AVL

数组和链表的区别

动态数组

Tags：sql,数据库