php+redis+mysql+laravel面试题总结（持续更新ing）

1，myisam 和 innodb
    什么是储存引擎？
        数据库的储存引擎决定了表在计算机中的储存方式，不同的储存引擎有不同的储存机制，索引技巧等
    储存引擎区别？
        初步区分的话是这样的，
        myisam表锁，不支持事物
        innodb行锁，支持事物，innodb支持外键
    补充说明：
        myisam建表之后会有三个文件(一个是frm表结构文件，一个是myd数据文件，一个是myi索引文件），myisam索引结构文件与数据文件是分开的，另外它的索引是非聚簇（也就是二级索引）所以说myisam的索引都需要回一次表.
        另外说明下，myisam索引文件存的是磁盘地址，过程是一次索引查询之后拿到磁盘地址（指针）。
        innodb建表之后会有两个文件（一个是表结构文件frm,一个是索引与数据文件ibd)

2，索引
    什么是索引
        索引是数据库中对一列或者多列值进行排序的一种数据结构，使用索引能快速的访问到想要的数据。
    索引都有哪些（mysql)
        mysql索引大概有5中
            主键索引
            唯一索引
            联合索引
            全文索引
            普通索引
    mysql索引数据结构演化过程
        二叉树-》红黑树-》btree-》b+tree
    联合索引遵循最左原则
    举例：
        一个表中有 id A B C D 5个字段。
        现在建立联合索引 A B C 
        能用到ABC的情况：
            select * from 表 A=? B=？C=？
            select * from 表 A=? B=？C>？
            select * from 表 A=? B=？C<？
            select * from 表 B=? A=？C<？-查询优化器
        能用到AB情况：
            select * from 表 A=? B>？C=？
            select * from 表 A=? B<？C>？
            select * from 表 A=? B like ？C<？
            select * from 表 A=? B between ？C<？
        能用到A情况 与上面AB类似
        
3，回表
    什么是回表？
        所谓回表，是指mysql查询数据，拿到相关数据的主键（地址（指针））然后再进行一次查询查到相关具体数据，简而言之若想拿到具体信息就需要俩次查询。
    聚簇索引&非聚簇索引
        mysql底层数据储存用的是b+tree数据结构；
        聚簇索引：叶子接点储存的是数据本身，所以聚簇索引不需要回表，一次就能查到整个真实数据。
        非聚簇索引：叶子接点储存不是数据本身，是一个地址（指针）or 主键等数据
    什么情况下需要回表？
        情形1，myisam数据储存引擎级结构决定了它的查询都需要进行一次回表操作
        情形2，覆盖索引不需要回表，
            什么是覆盖索引，覆盖索引就是例如：就是将A B联合索引起来，然后查询 (主键)id A B就是覆盖索引
        情形3，非覆盖索引，例如:建立联合索引 A B 然后查询的是 * 就都需要回表操作
    开发的时候需要注意什么？
        书写规范的sql语句。
        尽量建立覆盖索引，然后查询数据

4，mysql三范式
    第一范式，数据具有原子性，即每一列的数据都不能再拆分
    第二范式，建立在第一范式的基础上，所以非主键字段都要依赖主键，而不能依赖主键的一部分
    第三范式，建立在第二范式的基础上，非主键列只依赖主键，不依赖其他非主键
    

5，hash
    什么是hash?
            hash表，其思想主要是基于数组支持按照下表随机访问数据时间复杂度为O(1)的特性。
    什么是hash冲突？
        我们知道，对象hash的前提是实现equals()和hashCode()两个方法，那么hashCode()的作用就是保证对象返回唯一的hash值，但当两个对象计算值一样时，就产生了hash冲突。
        当我们对某个元素进行哈希计算，得到一个储存地址，然后进行插入时，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。
    哈希冲突如何解决？
        方法1，再哈希法，再哈希法又叫双哈希法，有多个不同的hash函数，如果遇到哈希冲突时，使用第二个、第三个再进哈希计算，直到没有冲突为止。
        方法2，链地址法（拉链法），例如HashMap，每个哈希表接点都有一个next指针，多个哈希表接点可以用next指针构成一个单向链表。
        方法3，建立公共溢出区法，在创建哈希表的同时，再额外创建一个公共溢出区，专门用来存放发生哈希冲突的元素，查找时，先冲哈希表差，查不到再去公共溢出区查。
        方法4，理解1，开放地址法（再hash法），当关键字key的哈希地址p出现冲突时，以p为基础，产生另外一个++++++++++++++++++++哈希地址p1,如果p1仍然冲突，产生另外一个哈希地址，直到找出一个不冲突的哈希地址pi，将相应的元素存入其中。
        理解2，开放寻址的核心思想是，如果出现hasn冲突（hash冲突），我们就重新探测一个空闲位置，将其插入。比如：我们可以使用线性探测法，当我们往hash表中插入数据时，如果某个数据经过hash函数hash之后，储存位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，如果遍历到尾部都没有找到空闲位置，那么我们就再冲表头开始找，直到找到为止。
        
    各种解决途径的优缺点

    redis采用的是拉链法（链表法）解决的冲突，
        redis中hash表接点中都带有一个*next，这样如果哈希冲突了，就采用单向链表的方式将值链起来。
    负载因子与rehash
        hash表中的负载因子 = 填入表中的元素个数 / hash表的长度
        hash表负载因子越大，代表空闲位置越少，冲突也就越多，hash表的性能会下降。
        hash表负载因子越小，代表空闲位子越多，则会造成内存不能合理利用，从而形成内存浪费。
        因此负载因子不能越大，也不能越小。要控制在一个合理的范围内。此时就需要rehash、渐进rehash
        rehash过程
            redis中，每个字典会创建两个hash表ht[0],ht[1].数据会储存再ht[0]表接点中。如果负载因子过小或过大。
            redis就会以ht[0].used字段扩展ht[1].size字段，ht[1].size = ht[0].used^2的2的N次方幂。然后将ht[0]中的数据一次或逐步转存到ht[1]中，数据转换过程中，会生成一个rehashidx标记0为渐进转换过程中，rehashids为-1时。转换完成。此时ht[0]节点表为空，然后删除ht[0]表。将ht[1]表设置为ht[0]，另外创建一个空ht[1]表节点。
    理解：
        字典结构定义：
          

  typedef struct dict{
                //类型特定函数
                dictType *type;
                //私有数据
                void *privdata;
                //哈希表
                dictht ht[2];
                //rehash索引
                //rehash不在进行时，值为-1
                int trehashidx; /*rehashing not in progress if rehashidx == -1 */
            } dict;

      
        hash表结构定义；
          

  typedef struct dictht{
                    //hash数组
                    dictEntry **table;
                    //哈希表大小
                    unsigned long size;
                    //哈希表大小掩码，用于计算索引值
                    //总是等于size-1
                    unsigned long sizemask;
                    //该hash表用的接点数量
                    unsigned long used;
            }

        hash表接点结构定义：
         

   typedef struct dictEntry{
                //键
                void *key;
                //值
                union{
                    void *val;
                    uint64_tu64;
                    int64_ts64;
                }v;
                //指向下一个hash表接点，形成链表
                struct dictEntry *next;
            } dictEntry;

            
    以上三个结构就构成了redis字典结构，为嵌套关系。

数据结构与算法
6，
    算法
        什么是算法？
            算法：是指用来操作数据、解决程序问题的一组方法。对一定规范的输入，在有限的时间内获得所要求的输出。一个算法的优劣可以用空间复杂度和时间复杂度来衡量。
        时间复杂度
            常数阶O(1)
            对数阶O(logN)
            线性阶O(n)
            线性对数阶O(nlogN)
            平方阶O(n^2)
            立方阶O(n^3)
            k次方阶O(n^k)
            指数阶(2^n)
        空间复杂度
            O(1)
            O(n)
            O(n^2)
    数据结构
        什么是数据结构？
            数据结构是计算机储存、组织数据的方式。一种好的数据结构可以带来更高的运行或者储存效率。数据在内存中是呈线性排列的，但是我们可以使用指针等道具，构造出类似"树形"的复杂结构。
        八个常见的数据结构
            数组(array)                |
            链表(linked list)         |
            栈(stack)                   | 线性数据结构
            队列(queue)              |
            
            树（二叉树|完全二叉树|b+tree）    |
            堆（heap）                                     |
            散列表(hash表)                               |  非线性数据结构
            图(graph)                                        |
            
            数组：
                数组的定义：

                        数组是一种线性表数据结构。它用一组连续的内存空间，储存一组具有相同类型的数据。
                什么是连续的内存空间？
                    首先，我们来说说内存，内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。在这些内存单元中，有些被其他数据占用了，有些是空闲的。
                    然而数据中的每个元素，都储存在小小的内存单元中，并且元素之间紧密排列，既不能打乱元素的储存顺序，也不能跳过某个储存单元进行储存。
                数组的随机访问
                    数组的随机访问是有一个寻址公式的，因为数据都储存在一块连续的内存单元格中切每个单元格都有自己的地址（计算机通过这个地址访问数据）且每个单元格大小都是一样的，公式如下；
                    a[i]_address = base_address + i * data_type_size
                总结：
                    数组是使用一块连续的内存空间，储存相同类型的一组数据，其最大的优点是数组支持随机访问，因为数组可以通过数组下表（寻址公式）快速访问对应元素，时间复杂度为O(1)。
                    数组在删除元素和插入元素这两个操作比较低效，是因为数组为了保持数据的连续性，会涉及到数据的挪动，平均时间复杂度为O(n)。
                    
            链表：
                链表是一种顺序结构，由相互链接的线性熟悉怒项目序列组成。因此，必须顺序访问数据，并且无法进行随机访问。链表提供了动态集的简单灵活的表示形式。
              

  伪代码：
                    typedef struct LNode{
                        ElemType data;//数据域
                        struct Lnode *next;//指针域，指向后续
                    }LNode,*LinkList;

            树(二叉树)：
                

伪代码：
                    typedef struct BiTNode{
                        TElemType    data;
                        struct BiTNode *lchild,*rchild;//左右孩子指针
                    }BitNode,*BiTree;

                
        
        八种数据结构的优缺点：
            1，数组
                优点：按照索引查询元素的速度很快
                缺点：数组的大小在创建后就确定了，不方便扩容；数组只能储存一种数据类型；添加，删除元素的操作很耗时间，因为要移动其他元素
            2，链表
                优点：链表在插入、删除的时候可以达到O(1)的时间复杂度并且链表克服了数组必须预先知道数据大小的缺点，从而可以实现灵活的内存动态管理。
                缺点：含有其他接点的引用，占用内存空间大；查询元素需要遍历整个链表，耗时。
            3，栈
                栈按照'先进后出'的原则来储存数据，先插入的数据会被压入栈底，后插入的数据在栈顶，读出数据的时候，从栈顶开始依次读出。
            4，队列
                与栈不同，队列对两端进行定义，一端叫队头，另外一端就叫队尾。队头只允许删除操作(出队),队尾只允许插入操作(入队)
            5，树(注意考题-二叉树的遍历(先序遍历、中序遍历、后序遍历))
                1,二叉树：每个接点最多含有俩个子树，按照左右不同的表现形式又可以分为多种。
                2,完全二叉树：对于一颗二叉树，假设其深度为d,除了第d层，其它各层的接点数目均已达到最大值,且第d层所有节点从左向右连续的紧密排列
                3,满二叉树：一颗每一层的节点数都达到了最大值的二叉树
               B树
                一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于俩个的子树
            6，哈希表
                是一种可以通过关键码值(key-value)直接访问的数据结构，它最大的特点就是结合了数组和链表的有点可以快速实现查找、插入和删除。
                哈希函数在哈希表中起着非常关键的作用
                它可以把任意长度的输入变成固定长度的输出，该输出就是哈希值。
                哈希表是通过数组实现的，首先对key值进行hash算法得到一个数，然后对该数进行寻址算法计算，得到一个数组中的下标，通过该下标对数据进行存取，解决地址冲突常用方法有链表发
            7，栈（未完，待续）
            8，图（未完，待续）
番外篇：
    IO多路复用
        什么是io多路复用
            IO多路复用，一种同步io模型，单个线程/进程可以同时处理多个io请求，一个进程/线程可以监视多个文件句柄，一旦某个文件句柄就绪，就能通知应用程序进行相应的读写操作，
            没有文件句柄就绪时会阻塞应用程序，交出cpu.
            多路是指网络连接，复用是指同一个进程/线程。
            理解：一个进行/线程虽然任意时刻只能处理一个请求，但是处理每个请求时，耗时控制在1毫秒以内，这样1秒内可以处理上千个请求，把时间拉长看，多个请求就复用了一个进程/线程。这就是复用，这种思想类似于一个cpu并发多个进程，所以也叫做时分多路复用。
        为什么会出现io多路复用机制？
            同步阻塞io
                单线程时
                    服务器采用单线程，当accept一个请求后，在recve和send调用阻塞时，将无法accept其他请求，必须等待上一个请求处理完成，不能处理并发
                多线程时
                    服务器采用多线程，当accept一个请求后，开启线程recv,可以完成并发处理，但随着请求数增加需要增加系统线程，大量的线程占用很大的内存空间，并且线程切换会带来很大开销。
            同步非阻塞
                服务器端当accept一个请求后，加入fds集合，每次轮询一遍fds集合recv（非阻塞）数据，没有数据则返回错误，每次轮询所有fd会浪费cpu
        io多路复用
            服务器端采用单线程通过select/epoll等系统调用获得fd列表，遍历有事件的fd进行accept/recv/send，使其能支持更多的并发连接请求。
        io多路复用的三种实现方式
            1,select函数
            2,epoll函数，epoll只在linux下工作，epoll应用redis、linux
            3,poll函数
        区别

    二叉树(伪代码)
        二叉树结构伪代码
            
          

  typedef struct BitNode{
                TElemType data;
                struct BiTNode *lchild,*rchild;
            }BitNode,*BiTree;

            
        先序遍历的顺序创建二叉树
         

   status CreateBiTree(BiTree &T){
                scanf(&ch);
                if(ch == '') T = NULL;
                else
                {
                    T = (BitNode *)malloc(sizeof(BitNode));
                    if(!T) exit(OVERFLOW);
                    T->data = ch;
                    CreateBiTree(T->lchild);
                    CreateBiTree(T->rchild);
                }
                return OK;
            }

        先序遍历
            

void PreOrderTraverse(BiTree &T)
            {
                if(T)
                {
                    printf("%d ",T->data);
                    PreOrderTraverse(T->lchild);
                    PreOrderTraverse(T->rchild);
                }
            }

        中序遍历
    

        void InOrderTraverse(BiTree &T)
            {
                if(T)
                {
                    InOrderTraverse(T->lchild);
                    printf("%d ",T->data);
                    InOrderTraverse(T->rchild);
                }
            }

        后续遍历
          

  void PostOrderTraverse(BiTree &T){
                if(T)
                {
                    PostOrderTraverse(T->lchild);
                    PostOrderTraverse(T->rchild);
                    printf("%d ",T->data);
                }
            }

未完~！--待续