引言

本来自己查了很多资料,想自己写出来,结果下笔的时候发现别人已经把我想写的部分全部写出来了,而且比我想的还要具体,所以我就不写了,把链接放出了,顺便我补充一些

http://leenjewel.github.io/blog/2015/11/11/%5B%28xue-xi-xv6%29%5D-nei-he-gai-lan/

总结

由于内存分页在后面的lab2中也会设计,而且给出的资料写的非常详细,所以我就不多提了。这里提一下为了更好的理解什么内存分页的段选择子与CS的关系,我写了一篇关于CS寄存器的发展史

最后我提一下kern/entrypgdir.c手写的内存分页表

第一个entry_pgdir是页目录,第二个entry_pgtable页表,而且注意entry_pgtable是代表0-4M物理内存可写可读的真实内存地址

前面知道了目录和页表的作用,在现实系统中,一个目录下有1024个页表,但是这只有一个页表,而且它代表从0-4M连续的内存空间

PS:后面12位是权限位,只看前三位,可以知道是从(000-3ff)的高20位物理地址,由于我们声明了__attribute__((__aligned__(PGSIZE)))(地址4K对齐,其实意思是它真实物理地址后12位一定全部为0),所以直接取(uintptr_t)entry_pgtable地址就是页表地址,虽然后面加上权限位PTE_P + PTE_W,但是在寻找真实地址时都会屏蔽(只取前20位如),当初想了很久感觉取不到页表的真实地址,还以为有什么神奇的编译设定,后面查了很久资料才明白,所以这里提个醒后面我们会在lab2中正式接触内存分页技术,这里只是相当于设定了一个“常数”,后面会将器扩展变成“函数”。

引用

引言

本来自己查了很多资料,想自己写出来,结果下笔的时候发现别人已经把我想写的部分全部写出来了,而且比我想的还要具体,所以我就不写了,把链接放出了,顺便我补充一些

http://leenjewel.github.io/blog/2014/07/29/%5B%28xue-xi-xv6%29%5D-cong-shi-mo-shi-dao-bao-hu-mo-shi/

http://leenjewel.github.io/blog/2015/05/26/%5B%28xue-xi-xv6%29%5D-jia-zai-bing-yun-xing-nei-he/

ELF文件

首先你要知道什么是ELF,可以看一下这篇博客,简单来说就是编译完C后的机器码,前面加了一些数据表记录程序的分布情况

为了帮助我们逆向分析这些代码有什么,我们必须要借助两个工具

  • objdump
  • readelf

我们接下来就用实际例子解读mit6.828里面的引导和核心

引导

首先我们查看一下引导文件,在boot/目录下有两个文件

  • boot.S
  • main.c

两者是通过gcc编译器将汇编和C编译成为一个elf文件,具体在Makefile文件中(boot/Makefrag),我将它简单翻译一下

gcc -N -e start -Ttext 0x7C00 -o boot.out boot.o main.o

boot.omain.o就是boot.Smain.c编译后的文件,-e start意思程序从boot.Sstart中开始运行(这样就能从汇编开始执行),-Ttexttext代表代码段,也就是说直接指定代码入口地址为0x7C00,我们可以用readelf验证一下

mit-6.828-2014 ➤ readelf -h obj/boot/boot.out                         git:lab1*
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x7c00
  Start of program headers:          52 (bytes into file)
  Start of section headers:          4868 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         2
  Size of section headers:           40 (bytes)
  Number of section headers:         9
  Section header string table index: 6

我们读取了一下生成的elf文件头部,我们可以看到Entry point address这个字段,就是我们设定的0x7c00,要了解这个地址的含义我们必须知道虚拟地址和物理地址的区别,可以看一下这篇博客,接着我们看一下反汇编的汇编代码obj/boot/boot.asm中,我们知道现在0x7c00代表程序把自己当做在内存上的真实内存上面,但是不一定会真的存在这块上,所以我们称它为虚拟的

首先我们了解一个系统知识,因为电脑启动后会按照启动盘顺序,把每个盘第一个扇形区512B取出来,如果最后两个字节为0xAA55的话就把它放到内存上面的0x7c00上去,我们看一下我们生成的obj/boot/boot

使用hexdump obj/boot/boo可以看到(我把最后一行复制出来)

00001f0 0000 0000 0000 0000 0000 0000 0000 aa55

最后连个字节为0xaa55,且文件大小刚刚好512B,这时候你可以有一个疑惑了,我们知道gcc我们生成的boot.out的elf文件,但是这个文件还有头部存贮数据,我们如果把整个文件放到磁盘上,当程序在内存0x7c00处执行时,那么文件头部碰到的就是elf头了,所以
为了把机器码提取出来并生成合适文件(512B尾部为0xaa55),程序干了两件事

  • 用objcopy将elf文件中执行代码提取出来(相当于去掉elf头部)
  • 用脚本修改尾部两字节(在boot/sign.pl用了perl程序来将生成512B且尾部为0xaa55boot文件)

总结

后面将核心加载到内存,上面的给出资料写的很详细,我就不多说,只不过由于当前2014的版本同资料有点不同,这里我提一下

当前版本是将内核头加载在0x10000上,然后在把内核代码加载到0x100000上(前面4个0,后面5个0,我当初看错了,百思不得其解),并将内核地址映射到f0100000上。

引用

http://leenjewel.github.io/blog/2014/07/29/%5B%28xue-xi-xv6%29%5D-cong-shi-mo-shi-dao-bao-hu-mo-shi/

https://my.oschina.net/u/864891/blog/87965

端口信息

引言

Intel作为作为微处理器的航头老大,一直引导CPU的进步发展,也正是因为Intel是一个有着历史包袱的企业,所以站在现代CPU看起来,有一些非常奇葩的设计遗留下来,这些设计一开始是为了兼容,慢慢的将这种兼容又发展成新的功能,把“包袱”转换成“亮点”,段设计就是其中的一个很重要的代表,要想搞懂这个设计在不同的CPU的如何保持兼容和强化,我们必须要慢慢的把CPU的历史给捋顺。

前言

我们要介绍第一个CPU是8086,虽然Intel前面也生产了4004、8008、8080微处理器,但是8086基本上后面所以现代化CPU始祖,Intel后面生产的CPU都对8086兼容,所以可以说段这个“祸端”就是从8086种下来的

8086作为第一款的16位处理器,由于技术的问题,出现了一个严重问题寄存器只有16位,而地址总线却有20位,要想只通过一个寄存器表达地址的值显示无法实现,所以8086采用了一个段寄存器,segment × 16+offset(CS:IP),采用这个方式就能实现20位地址索引

段设计对程序影响

前面简单的介绍了段设计的原因,现在我们来看看这个设计的对16位程序的影响。

兼容性

由于段的存在,我们设计程序的时候可以更加自由,我们可以假设我们是在任何低16位置的内存上,只有到时切换程序时候切换段就可以

安全性

我们可以用相同的低地址存代码和数据,只需要切换段就行,而且我们也不需要考虑数据要多少空间,代码要多少空间,以便设定跳转地址

可以说段设计是16位程序的一个很优雅的做法,但是到了32位的时候程序不行了

32位处理器的改变

我们知道32位处理器的诞生带来了两件事,第一个就是寄存器有32位了,说明最大内存地址可以到4G了(0x000000-0xffffff),而且总线地址也有32位了。这个时候就很尴尬了,原来的段设计到这里就成鸡肋了。但是为了兼容,我们还是给他一个功能,段选择子,当然现代Unix操作系统没有用这个东西,只是在初始化的时候意思意思一下,具体可以看一下这篇博客GDB

总结

最近学操作系统感觉学了很多知识,总想好好总结一下细节,结果发现总有大神们早就写出来了,而且非常详细,我就不班门弄釜了,把下面的lab好好思考,提炼出自己的知识。

引言

本文是基于mit6.828 的lab1对操作系统的思考,网上有不少关于lab1的博客,大部分都是介绍如何完成lab1的问题,介绍的比较详细的有这个博客,在这里我就不从问题出发,建议大家看完上面的博客在看我这篇博文,我这篇博文就是从把我遇到的疑惑提炼出知识点,然后再把这些知识点串起来

实验目的

作为操作系统的第一个实验,在完成lab1我们主要目的就是要了解什么是操作系统,后面的lab都是在这个基础上搭建完善好系统的各种功能,就好像你画一幅画,第一步你先把人物的轮廓外形画出来,接下来你在把人的鼻子耳朵眼睛等等慢慢画出来,所以第一个实验非常重要,如果不把骨架搭好,你的操作系统再怎么豪华强大也是空中楼阁,所以我们在这个lab上一定要花上很多时间,万事开头难,只要攻克了这个,操作系统也就离你不远了

前言

谈操作系统之前必须得谈谈什么是计算机,因为我们的操作系统是运行在计算机上面的,操作系统与计算机关系密切,我们可以用一个很贴切的比方,假如你想了解手套为什么长成那么奇怪,那么你得先举起你的双手看看。

闲话不多说,进入正题,计算机最核心部分就是CPU,记得电脑刚发明出来的时候,编程只能通过穿孔卡片,当然计算机发明这么久,CPU的核心功能基本上没有变,还是只能通过“穿孔卡片”,只不过我们编程语音将我们的使用的语音如C,Python等变成“穿孔卡片”,这里有个非常重要的概念:指令。也就是每个CPU的是每次只能执行一条指令。当然第二个重要的就是内存了,前面说了CPU是必须要通过”穿孔卡片“来编程的,但是随着程序愈来愈大,我们必须要使用一个东西来存贮“卡片”,所以内存孕育而生了,其实很多感叹电脑这个词实在是太贴切了,人脑可以处理问题,电脑也可以处理问题,人脑有短期记忆长期记录,电脑有寄存器(短期记忆)内存(长期记忆)。

简单的谈了谈计算机,我们提出两个重要的前提

  • 计算机通过顺序读取一条一条指令来工作
  • 计算机从内存获取指令

所以操作系统的就是在内存上面运行自己并帮助其他程序的一个大程序,总的来说它就是内存上面的一段程序,当然它的功能就是好好在它一亩三分地上面“分封诸侯”,维护自己的“王位”。

由于一开始它只是待在软盘或者磁盘等存贮设备上的一段程序,接下来我们就看操作系统如何“上位”内存的“宫斗大戏”。

上位篇

在操作系统“上位”之前,其实计算机还进行了一个小操作系统(BIOS)运行,具体的流程可以看这篇文章,如果把电脑看做人的话,BIOS就是我们的脊髓,它控制我们的身体四肢(硬件),但是却无法灵活的操作他们(比如非条件反射的膝跳反射),但是它却不可少,少了它就成植物人了。BIOS的作用总结起来就是感知硬件,调控硬件(比如CPU电压,内存频率)。

BIOS与操作系统最密切的一个地方就是设置启动盘,大家可能大多时候都是听文件文件比较多,但是文件这个概念其实是操作系统的,在没有操作系统之前是没有文件这个概念的,只有盘这个概念,比如一块硬盘、一张软盘、一个U盘,所以BIOS的一个重要工作就是选定一个存储硬盘,然后读取上面的程序运行。

所以我们从这时候可以得到一个结论,安装操作系统,只需要按照BIOS的规定把程序放到某一个存贮设备(磁盘、U盘、软盘)专门位置上(一般是头部开始),开机后然后就静等BIOS把程序加载到内存,就完成了“上位”过程。

我们已经知道操作系统的外部条件,接下来分析一个操作系统到底该有啥

操作系统结构

首先我们要回顾一下操作系统的发家史,刚开始是没有操作系统的这个概念的,随着在电脑上要运行的越来越多,每个程序都要写大量底层代码来操作硬件这样无疑每个程序越来越来臃肿,所以我们需要让操作系统管理来管理硬件,这样不但能够提供程序兼容性(一次编译、到处运行),而且能高效利用硬件(操作系统专供)。所以操作系统也就是程序的分工的产物

接下来我们看看操作系统的发展历史,大家都知道汇编语言是除了机器语言最接近底层的一种语言,第一个Unix系统一开始也就是使用汇编编写的。但是汇编语言不易于维护,所以1973年汤普逊和里奇用C重构了Unix,但是部分与硬件接触太大的地方还是必须使用汇编(in、out端口,操纵指定寄存器等),所以现代操作系统还是用C与汇编混合编写的(C占大部分),当然最后都会编译成机器码,所以我们从机器码角度来看,最后的结果都是相同的,不同的是我们使用不同的工具来生成机器码

前面我们介绍了启动盘,其实BIOS给我们只是从启动盘上面取了一小段数据(第一个扇形区)放到内存上面(512B),然后执行那小段上面的机器码,所以接下来就有一个问题,随着我们的操作系统功能越来越完善,取出来的代码肯定不是全部代码,代码只有放到内存上面才能跑,所以前人就把代码分成两部分,一部分称作引导,另一部分才是核心代码,引导作用就是把核心代码放到内存上面去

所以操作系统被分成两部分

  • 引导
  • 核心

这里比较有意思的地方就是引导和核心如何交换程序控制权,由于要讲解必须要牵扯代码,所以我把这部分分离出来,放到这篇博客上面,要了解细节可以看这篇博客。

现在我们假设你已经知道引导将核心代码加载在了内存上面,现在我们就从这里开始分析,堆栈作为程序的基础,首先我们要提一下堆栈

堆栈

什么是堆栈呢?看下面这张图

堆栈

堆顶为大地址,我们使用的时候只要不断把栈顶往下推,就能将线性内存变成一个数据结构。当然有个问题,我们必须要知道什么地方是栈顶,现在我们想想操作系统必须要放到内存的某一个地方,假如放到低位置,那么我必须要记住操作系统的最高位置,如果不这样做当堆栈顶到操作系统的存贮地址,那么操作系统就被破坏了。所以我们只能把操作系统放到高的内存地址,这样我们既能安全的使用堆栈,而且保证了操作系统的安全

所以我们接下来就谈谈由于这个设定引发的一系列问题

操作系统的高地址

在lab1中,操作系统的起始代码被设定为0xF0100000的高位

从这个地址我们可以分析出来什么0xF0100000,因为我们知道32位操作系统最高只能有4G内存,也就是2的32次方内存,这个地址代表的是系统最后面的255M内存的空间,也就是操作系统给自己留了255M剩余内存,给前面保留了(4G-255M)空间

操作系统这个设计是非常好的,不仅给自己留下扩展空间,也给其他代码带来便利,就是从0-(4G-255M)这部分内存随便用,怎么改都不会出问题

从现在角度来看,个人电脑随便都是2G、4G内存,但是在70\80年代,几M内存都很很大的存在,如果我内存没有4G这么大,那么这个操作系统就无法使用了,而且你留下256M给操作系统,有的时候我整个电脑内存都没有这么大,留下那么多,就是浪费

所以最后他们想出来一个办法,就是现实和理想之间放一个转换器(MMU),也就是动态内存管理。操作系统也不管你机主有多大内存了,我假设你有4G,当你用一块,无论是什么位置,我从空余的地方给你取出来,假如你没有4G,我就把一部分不常用内存值的放到磁盘上面,这样通过这样这样的操作的实现内存的高效利用。

操作系统对内存这种骚操作就相当于在更高的维度上建立了一种抽象,不论底层硬件怎么变(内存大小不同),我高层都不需要变,只需要底层把根据实际情况依次映射,这样无论你换多大内存,我都不需要重装系统。

这种映射不通过代码很难将清楚,所以我这里也不提太多,如果你想知道怎么映射,硬件如何配合,你可以看我这篇博客,详细介绍了内存分页的骚操作。

总结

至处到这里我们的操作系统之旅就结束了,我们成功在引导帮助下上了内存,也使用了提高操作系统的地址保证了堆栈的正常使用,接下来就是操作系统的各种附加功能,我们也会在接下来的lab中继续讲解。

lab1不止介绍了这两个地方,但是在lab1中我觉得最重要的地方就是要知道操作系统是什么,它从哪里来,它要到哪里去,操作系统毕竟牵涉到硬件,很多硬件知识我们不一定能搞懂,比如说要切换哪几个位到保护模式,怎么输出端口才能读取扇形区,但是我们必须要搞懂他这样做的原因,这也是我在这篇里面谈了很多操作系统历史的原因,希望在理解操作系统上面能给大家带来一点启发。

在最后的话,我谈一谈我对入门这门课的感受吧,我算编程基础还算比较扎实,但是在一开始学习的过程中一脸懵逼,C语言的各种骚操作,汇编与C疯狂混合,看惯了脚本语言的我,对这种改一下就编译不过的“硬骨头”异常难受,一开始根本看不下去,有的时候看几行代码,查资料好几个小时,而且资料特别难找,你不知道这种骚操作有啥意思,在这里还得感谢学习过这门课的学长学姐们,在网上无私的把自己的感受分享出来,慢慢的根据他们的资料和自己的调试还有自己找资料,慢慢的把这个代码一行一行搞懂,搞懂之后特别感慨,其实也不是很难,难的是要把你知道的所以知识点串起来,然后你就能搞懂为什么要这么做,所以我推荐大家还是多看代码,多去思考为什么要这么做,必须要自己的思考在里面,如果单纯的知识为了完成实验其实很简单,但是难就难在把这门课琢磨透,搞懂他们为什么要这样考你,毕竟大家最后的目的都是自己做出自己的操作系统,只有了解的透彻,才能“破而后立”搞出自己的创新,而不是复制他们的壳子,所以加油把每一行代码都搞懂,多思考,不要骄傲,毕竟这只是教学类的操作系统,要想自己写出来还得不懈努力。

接下来还有6个lab需要完成,终于迈出的第一步,希望在年前能够完成所有的实验吧!!!加油!!!

引用

“C语言虚拟内存表”

引言

一开始想直接做一个操作系统,但是万事开头难,学习操作系统需要太多基础知识了,所以就按照网上推荐先学习mit6.828的课程,先把xvf6操作系统搞懂,然后在来实现自己的操作系统,下面就是学习这个课程的体会,按照各个lab的顺序,介绍自己的心得体会

课程的地址是: mit6.828
PS:由于mit6.828课程仓库需要翻墙,所以我把clone下来放到我的github仓库,我的仓库里,大家可以clone下来(我会逐渐完成所以的实验)

目录

引言

最近逛知乎的时候看到一篇知乎回答很有趣,也给了很深的感触,自己对于操作系统、数据库、HTTP用的都非常熟练,但是也从来没有去想怎么怎么实现或者背后深层次的原理

以前刚开始学习的时候自己也看过很多关于操作系统、数据库的书,但是就像走马观花一样,很多书就是过了一遍脑子,然后就没有了,在2017年下半年自己也开始尝试把自己以前只是了解只是会用的东西拿出来咀嚼咀嚼,并在这个过程中写出一些自己觉得还是有点干货的博文。而且我也比较享受把复杂的问题简单话的过程。

操作系统、计算机、数据库、编程原理在我看来都是非常复杂庞大的东西,在2018年,希望能够将上面这些复杂的东西搞的简单一点,当然在这个同时我也会将我将问题简单话的过程中分享出来。

当然这些东西都太过宽泛,比如操作系统。很多人刚开始学习编程了解了操作系统概念,还有听到很多牛人都说自己写了一个操作系统都会在心里暗暗的立下一个Flag,自己也要做一个操作系统,但是很多人的热情慢慢的被无数的复杂概念慢慢磨掉,最后能坚持到做出一个完整的系统没有几个。作为一个普通人,我们没法一口吃下一个很大的“饼”,当然你如果叫爱因斯坦给你造一个原子弹,它也只能拍拍手跟你说我只能证明它能造出来。所以有效的解决问题的方法是将问题分解,或许最终我们最终造不出操作系统,但是我们对操作系统也能更深一步了解。

操作系统

首先谈谈操作系统,其实我们对操作系统的理解大致都停留在开关机。我们要分解的问题就是我们对这个“黑盒子”的疑问

  • 操作系统如何管理硬件,比如说鼠标移动点击、键盘输入
  • 操作系统如何让多用户使用
  • 操作系统如何在多用户的情况下区分每个用户
  • 操作系统如何分配内存,如何限制用户的内存
  • 操作系统如何管理文件,如何避免文件被同时写入
  • …..

当然我这里只是列举了一些直观的问题,在解答这些问题的时候,我们会逐渐衍生出各种问题,最终我希望所有的问题都能被简单话

数据库

数据库我算使用的比较多了,但是对数据库背后的机制也是懵懵懂懂,只知道他能保证这些功能,比如事务的原子性、一致性、分离性、持久性。

我觉得了解数据库就是要了解它是如何实现这些特性的,当然这个问题也很宽泛,我们可以尝试分解成

  • 数据库如何将输入复杂的查询分解成为数据库的操作
  • 数据库如何避免死锁
  • 数据对于插入删除异常如何解决
  • …..

其实在我看来数据库可以分解成两大块,一个是编程语音解析(SQL),一个是高效的存贮(Database)

所以了解数据库也可以尝试了解编译原理,了解如何实现解析SQL,所以接下来我就不提编译原理了

总结

其实想想自己的这种把复杂问题简单话就是华罗庚先生曾说的一句话:“把书由薄变厚,再把书由厚变薄”,首先我们得把这些看起来很简单的问题复杂话,最后慢慢的把这个复杂的问题简单话,这样你才能真正的把这个问题给搞懂。

对于我来说,从小或许受应试教育的影响,自己只学会了复杂问题给解决,但是不懂得解决后再把复杂问题简单话,所以看起来我懂很多复杂问题,但是其实换一个场景,换一个问题就一知半解了。所以自己慢慢的开始改变自己的方法,不满足于解决问题,而着重于简化问题,希望自己的一点经验也能给后来人一点启发。

本篇博客主要基于这篇博客的扩展,建议阅读前先阅读这篇博文,这篇博文详细介绍AVL树的实现原理,完整代码在githubavl.go文件中

浅谈”树”这种数据结构
Github
可视化页面

引言

AVL树是在对二叉搜索树的一种优化,通过构造一棵高度平衡的二叉搜索树从而实现提高空间利用率,所以在了解如何实现之前,必须了解如何构造一棵二叉搜索树,你可以阅读我的这篇博客了解如何构建一棵二叉搜索树,虽然我是用Go来实现的,但是不必了解太多Go方面的知识,我在博客中尽量使用图片的方式来介绍实现原理

二叉搜索树实现原理

由于AVL树本质上也是一棵二叉搜索树,查找并不会改变树的性质,所以AVL的查找也是同二叉搜索树的查询相同,所以这里就重点介绍如何实现“增”和“删”

树的字段

在开始介绍如何实现“增”、“删”之前,我想提一下AVL树的存贮字段,在wiki上面的AVL和很多资料上面,AVL的树结构分别由下面四个组成: Val、 Left*、Right*、Parent*。

Val代表树存贮的值,Left、Right、Parent代表三个指针,分别指向左子树,右子树,父亲,而在我的实现中,我去掉了父亲指针,对于讲解来说,使用一个父指针能很好的解决从子遍历到父亲的经过,但在实际的应用中,我们完全可以使用一个列表存贮从父亲到儿子之间的值,这样的话,能实现一样的功能,而且能节省存贮空间(每个子树都少了一个父指针),但是相应的程序也变得比较复杂起来。

虽然我在讲解的过程中会直接获取节点的父节点,但是在实际的代码实现中,是通过获取从列表中获取该节点的父节点。

AVL树的“增”

引用

https://en.wikipedia.org/wiki/AVL_tree

本篇博客主要基于这篇博客的扩展,建议阅读前先阅读这篇博文,这篇博文详细介绍二叉搜索树的实现原理,完整代码在githubbinary.go文件中

浅谈”树”这种数据结构
Github
可视化页面

引言

之所以使用Go来实现,个人还是比较喜欢Go的,作为一个基础数据结构,Go用来实现这个速度比Java、C++都快,而且相比Java也能节省内存,而且我也不喜欢换使用冒号。

二叉搜索树的基本功能

作为一个树结构,主要必须实现三个功能,查增删(当然有改,不过改是删和增的结合所以就不算在里面),当然二叉树还能帮我实现一些额外功能,比如寻找最大值最小值等等,实现一颗二叉搜索树必须要保证在“增”和“删”的时候保持树结构不变,也就是保证还是一颗二叉搜索树

什么二叉树是二叉搜索树呢,二叉搜索树只需要保证一点

  • 任何一个节点,它的左子树(不为空)所有值小于这个节点值,它的右子树(不为空)所有值大于这个节点值

所有我们在实现增删的时候必须要牢记这点,而且我们也可以知道在你开始对这颗二叉树进行增删的时候,它一定已经满足了上面这个条件

标准的二叉树

如何在上面这颗标准的二叉树里面查询到我们想要的值呢?我们知道一颗二叉树只需要知道根节点(上面的10)就能通过遍历得到所以的节点的值,所以我们在实现中声明一个二叉搜索树的时候只保存一个root节点,通过这个节点,我们就可以实现所以的增删查改功能了

为了找到每个值a,我们依次要在每个节点上对值进行比较,因为每个节点的值代表已经将这堆数据分成两个部分,一堆比这个值大在右边,一堆比这个值小在左边,这样只要最终能找到一个那个值的最小区间的对应值(找到)或者找到一个为空的叶节点(代表没有找到),

通过最简单的查找,我们可以反推出一个理论,假如我们需要插入一个值,我们只要先尝试去寻找到那个值,假如找到了,因为已经存贮了就不插入,假如没找到就会找到一个为空的叶子节点,那样只要在父节点将这个为空的叶子节点替换成这个值为a的节点,我们就完成了插入

所以查找和插入是相对的,知道怎么查找就知道怎么插入,接下来我们详细介绍如何删除,这个非常关键,因为它是后面要介绍的高级树实现高效的删除的关键

删除

我们还是以上面那种图举例子,删除我们最先想到的是删除12,17那些节点,直接删除掉对二叉树没有什么影响,但是如果我们要删除那些带有节点的呢?我们先简化问题,先看一个只有两个节点的树

双节点树

我们要想删除10,有两种可能

左移

右移

一种是将左边值移过来,一种是将右边值移过来,这两种都不会破坏二叉树的平衡,现在我们假设我们倾向将左边的值移过来,我们再回到上面那棵标准的二叉树,如果我们要删除掉10节点,我们要把那个值移过来,我们直接在可视化界面进行这个操作

删除10后的标准二叉树

我们发现,我们只需要将7和放到10的位置上就完成了一次删除的操作,而7与10的关系是,7是10左边的那堆值最大的,用一个通俗的话来说,完成改朝换代的关键就是要找一个能镇的住手下的人,由于“10”挂了,在左边只有“7”能镇住左边,所以”7”升官直接跑到“10”的位置了

根据这个原则我们将情况分成三种

  1. 左右子树都为空,直接删掉
  2. 左边子树或者右边子树有一个为空,将不为空的子树提上来当做删除的节点
  3. 左右子树不为空,将左边最大的值提上来替换删除的节点

对于第三种情况,为了编程方便,我们考虑一种情况,如果左子树的右节点有没有值(比如说上面的5节点),如果它右节点有值,那么左边的最大值肯定出现在,左子树的右节点上(就像上面左子树出现在5的右节点的7节点上面)。然后我们继续判断“7”节点有没有右子树,这样循环下去,我们总能找到一个节点没有右节点,这样我们就找到左子树的最大值了。

在上面这种情况下,我们将这情况分成两种

  • 如果左子树的右节点有值(循环下去找到一个节点右节点没有值)
  • 如果左子树的右节点没值(那么第一个左子树就是最大值)

具体的代码binary.goDelete(寻找节点)方法和delete(删除节点)方法中

总结

总的来说,二叉搜索树的插入是最容易理解的,但是删除的话要考虑不同四种的情况所以还是稍微需要点时间理解一下的,小小的一个二叉搜索树也花了近200行代码实现,但是相比后面的AVL树、红黑树的近千行代码来说,二叉搜索树还是比较简单的,而且后面实现的高级树结构基本上都是依赖二叉搜索树的实现(必须要按照二叉树的增删满足二叉搜索树的原则),所以我们对二叉搜索树的增删必须理解透彻。

引用:

https://en.wikipedia.org/wiki/Binary_search_tree

一直以来我对树这种数据结构就比较头疼,随便找一个红黑树的博客,大部分都是在谈怎么旋转怎么插入怎么删除,将算法讲的头头是道,但是就算你看懂了也不懂为什么要这样做,所以我们这篇博文就从可视化的角度,慢慢的介绍这些树的来世今生。

引言

首先给大家推荐一个神奇的网站,我们这篇博文很大程度上都是依托这个网站从可视化的角度分析各种树

网站的网址是http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

接下来我们从易到难分别谈谈下面这些树结构

  • 二叉搜索树
  • AVL树
  • 红黑树
  • Splay树
  • Trie树
  • B树
  • B+树

你可以点击下面高亮的标题尝试这种树结构的可视化操作,当然我在谈的过程中默认你已经打开可视化界面网站。

在开始介绍各种树结构之前,我们先谈谈为什么我们需要树这种结构。

假设我们一开始都有一个“柜子”存放东西,当我们东西很少的时候,我找东西的时候只要在柜子里面翻一翻就能找到,当我东西越来越多,在柜子里面找东西消耗的时间越来越多,这时候我就把柜子分类,让每一个柜子的东西都是固定的,这样我们查找时候不会在一个柜子里面寻找很久,这样无论你有多少东西进来,我查找的时间基本不会太长。

所以树这种数据结构就是为了解决当数据量越来越大的时候相比与线性查找时间基本不会太长。对树查找和线性的区别我们可以看一下这个可视化界面

线性搜索与二分查找

通过输入查找344,我们发现线性搜索花了15步才搜索到,而二分查找只需要2步,而且随着数据越来越大,线性搜索花的步数直线上升,而二分查找只会维持用Log(N)的步伐增长。

树的结构基本上都是基于二分查找,但是在维护这个查找树的方法上各种树有各种优化方法,接下来我们就从可视化角度来依次介绍各种树的原理和优缺点。

二叉搜索树

这个树可以称作所以后面变种树的鼻祖,基本上所以后面的树都是基于这个树的不足之处进行改良达到其各自的目的。

我们现在尝试构造一棵二叉树,我们依次插入3,2,4。然后一棵标准的二叉树就出现在我们面前,在我们插入的过程中,我们可以清晰的看到,第一个插入的变成了母节点,而且插入程序实现的非常简单,首先跟母节点进行比较,如果比母节点大,从母节点右边下滑,然后依次找到最后一个为空的节点把自己插入进去。

单调递增二叉搜索树

我们接下来尝试一下如果输入一个连续递增的数组进去,比如1, 2, 3, 4, 5,我们发现这个二叉搜索树会逐渐把所以的值放到右节点上。这时候我们我们尝试搜索一下5,我们发送这个二叉搜索树需要5次查询才能得到最终结果,这个基本上等同与线性搜索。

这里我们就发现二叉搜索树一个致命缺点,它容易造成一种空间的浪费,虽然这个树看起来很“高”,有5层,但是利用率极低,每层只有一个树,这样不但查找的时候效率不高,而且插入的时候效率也不高(很可能需要“爬”很多层)。

二叉树搜索树实现起来非常简单,只要用一个while循环就能完成插入查找等功能,但是由于它结构控制太低,它对数据要求要很高,它时候依次插入那些无序数字,而对那些有序数据来说,二叉搜索树等同与一个数组。

所以我们接下来介绍下面改良树,看看其他树是如何提高的空间利用率的,由于这篇主要是简单的谈一下这些树的优缺点,如果你想了解如何实现这样一课时可以看一下我写的这篇博文,详细介绍了如何使用Go语言实现一个高效的二叉搜索树,如果你想彻底了解下面高级的树的实现,强烈建议一下了解一下二叉搜索树实现的方法,因为后面所以的树实现的前提必须满足是一个二叉搜索树,这点非常重要。

二叉搜索树Go实现

AVL树

1962发明的AVL树现在还生龙活虎的活跃在Windows进程地址空间管理,虽然作为最早的平衡二叉树现在有点干不过后面的年轻的小伙,但是作为前辈,后面小伙很多地方都是借鉴前辈的,所以我们有必要隆重介绍一下这个老前辈。

首先要说明一下什么是平衡二叉树,前面我们也看到了,二叉搜索树有个弊端,它有可能子树高度不一样,比如说1,2,3,4,5那个母节点1的左子树高度为0,右字数高度为5,平衡二叉树就没有这个问题,它规定所以节点子树高度差不能超过1,这样规定的话我们的树空间利用率就能基本上达到100%了。

AVL树就是一颗高度平衡二叉树,它的要求也非常简单,就两个

  • 必须是二叉搜索树
  • 必须是平衡二叉树

成为一个二叉查找树非常容易,但是为了必须满足平衡二叉树条件,这里我们给每颗树定义一个高度,默认空为0,这样就可以计算左右子树的高度差是否在-1和1之间判断是否是平衡树。

了解了这个之后,我们回到web页面,我们输入1,2,3看看AVL树如何避免像二叉搜索树一样过度生长

插入前

插入后

我们从这两幅图可以看到,插入前AVL树高度为3,经过单旋转后,将2旋转到1的位置,然后让树又满足平衡二叉树的条件和二叉搜索树的条件。让我们思考一下旋转的意义。

旋转的意义

第一旋转并没有改变二叉搜索树的特性,我们将二叉树看做一个一个小区间组成的区域,旋转将区间整体移动了,所以我们保持住了区间的稳定,而且我们把旋转的支点看做中心,我们发现通过一次旋转后,支点左右之间的数量发生的变化,其中一方增加一个,其中一个减少一方,通过这种方式,把高度差由2转成0

所以我们在插入和删除的时候造成的高度不平衡可以通过正确的旋转达到一个高度差的减少。而且我们可以很轻松的推断出在插入和删除的时候只需要通过有限的旋转就能实现树的平衡,但是我们也会发现这个平衡是非常严格的,每次插入删除的时候,删除或者增加的那条“路径”(从根节点到修改的节点)的各个节点的高度都会发生变化,所以我们需要检查和更新整条路径上高度差(也称平衡因子)是否满足平衡条件。

直接纪录每个树的高度并且约束高度差的方法能够很好的规避像上面二叉搜索树造成的空间利用率低问题,但是对于增添和删除操作频繁的数据来说,AVL树并不是一个很好的解决方法,因为每次删除和增加都必须检测路径上的高度差,虽然旋转比较高效,但是每次检测和修改高度会让这个算法花费太多时间在这个严格的条件上面。

总的来说,AVL树是比较好理解的一种平衡树算法,通过这个树的各种旋转操作,我们能很清晰的发现二叉树是一种很神奇的数据结构,一方面它可能是混乱的(分支混乱),一方面它又是整齐的,通过“扭动”它的身躯,将数据平均的分摊在根节点上面。我非常推荐你在这个可视化界面上通过一步一步将单独递增或者递减的数据插入AVL树中,你会发现AVL通过一次一次的“扭动”,将数据向根节点另一个方向传输过去。

这里我也不详细介绍AVL树实现的具体原理,如果你想了解更底层的实现,可以看我下面这篇博客

AVL树的实现原理

红黑树

在AVL树发明10年后鲁道夫 贝尔发明了红黑树,直到现在红黑树还依旧在C++的STL、Java的HashMap中发挥着重要作用,只所以要先介绍AVL树再介绍红黑树,因为从我的理解上来看,其实红黑树和AVL树原理都是类似的,只不过红黑树修改了AVL树的缺点并且将AVL的平衡原理进行了抽象话。

从数据结构上来看,红黑树相比于AVL树来说,只是将存贮高度的值换成了存贮颜色的值,从空间的角度上看,红黑树用一个二进制bool值(1Bit)换掉一个存贮int值(4Bit),节省了3Bit的空间,从增删所需要的操做来看,AVL树旋转可能需要lnN 步操作,而红黑树增不超过2次旋转,删不超高3次旋转,在增删效率上远远优于AVL树。所以我们有一个疑问为什么红黑树能用更少的空间实现更高的效率呢?

回答这个问题之前,我们再捋捋AVL它的实现原理,前面介绍了AVL实现平衡的原理的就是使的左右子树高度差维持在[-1,1]之间,高度差这个东西,你想想高度这个东西其实它就是母节点到叶子节点的路径,所以高度差我们翻译一下就是左右子树路径差,现在我们把平衡后的AVL树条件更加严格一点,我们规定左右子树路径差为0,也就是左右子树高度一样。

满二叉树

在上面那个严格的条件下,假如我们要新增一个到树末端,假如它加在像上面这样满二叉树上面,那么左右子树高度就立刻不相同了,但是对于一个AVL树来说,在这颗树上末端插一颗树并不会影响树的平衡,所以我们要想一个办法让插入这个值“不算高度”,这时候我们一想,如果我们把树节点分成两种颜色,一种红色一种黑色,红色不算高度,黑色才算高度,那样虽然我现在条件很苛刻“左右子树高度必须一样”,但是如果插入的是红色,那么就能很轻松的实现上面的条件。

好了我们通过上面的操作成功的将高度变成了黑高(黑色节点的高度),而且满足了一种更加严格的条件“左右子树黑高必须相同),假如说前面AVL树的高度差为[-1,1]之间都能实现高空间利用率的,那么在这种更加严格的条件下也能满足,但是现在又出现一个问题,我们看下面这棵树

不平衡树

当我们插入节点3的时候,由于插入一颗红色你把红色节点不算高度,所以在前面的约束条件下,插入3满足条件,但是实际上这棵树并不是一个平衡AVL树,为了避免这种情况的发生我们必须要做一个约束,我们要约束红色节点不能太多,所以我们就约束红色节点后面只能是黑色节点,这样路径上最少都会有一半都是黑色(红色黑色相同)。

我们现在得到两个约束,现在我们来说思考一下这两个条件的约束到底给我们带来了什么

  • 黑高相同
  • 红后面必须为黑

首先对于黑色节点来说,这棵树是高度平衡的(假设它只能看到黑色节点),高度差为0,但是对于红色节点来说,这棵树有可能是不平衡的(假设有N个黑节点,红色高度差可能有N-1),所以从整体上来看,红黑树牺牲了一定的平衡性换来了插入删除的高效性

这个高效性表现在哪呢?第一它不在需要更新所有的高度差,它只需要对受影响的路径上的有限节点进行染色就能实现再次的平衡,其次由于它不在需要高度的平衡,所以它能容忍树上的红色的不平衡现象,来减少旋转变化的次数。

前面我们分析了AVL树旋转的意义那么对于红黑树来说,旋转的意义是什么呢?

红黑树的旋转意义

前面我们知道了在AVL树中每一棵树都是独立的个体,所以每次旋转都是一次运输,将树按照节点扭动,但是对于红黑树来说,它要处理的情况是黑树高度的不同,当需要搬到的也是黑树,它的目的就是将黑树的高度平衡,对于红色的树来说,它更像一种胶水,它能保证当数据不平衡的时候(所以的树不可能全部变成黑树)还能使黑树保持一种平衡,从而使一棵树变得相对平衡。

所以红黑树的旋转的意义同AVL树是类似的,只不过红黑树在旋转的时候要更加注意,它不但要考虑我们要如何在不平衡的节点上平衡黑高,而且要考虑我们平衡了这个节点的黑高有没有对其父亲的黑高造成影响。

对于红黑树来说,由于颜色是可变的,所以着色(改变颜色)也是一种手段,而对于AVL树来说高度是固定的,只能通过旋转来改变,所以单独讲红黑树的旋转是没有意义的,或许有的时候只需要通过旋转就能实现黑高的统一,或许通过简单着色也能实现黑高的统一,但是只使用一种手段是不能高效的完成所以的条件。所以在我看来着色和旋转是相辅相成的

也正因为我们多了一个着色的手段,所以红黑树比AVL树在某些方面更加高效,随着而来也是更加复杂难懂,但是总体来说AVL和红黑还是类似的,在这里我就不深谈如何实现红黑树,如果你想了解如何实现红黑树,可以看我这篇博客

红黑树的实现原理

剩余的四种树的简析会待代码实现后陆续更新

引用

https://en.wikipedia.org/wiki/Binary_search_tree

https://en.wikipedia.org/wiki/AVL_tree

https://www.cnblogs.com/vamei/archive/2013/03/21/2964092.html