这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战

内部类

Java 类中不仅可以定义变量和方法，还可以定义类，这样定义在类内部的类就被称为内部类。根据定义的方式不同，内部类分为静态内部类，成员内部类，局部内部类，匿名内部类四种;

内部类是个编译时的概念，一旦编译成功后，它就与外围类属于两个完全不同的类（当然他们之间还是有联系的）。对于一个名为OuterClass的外围类和一个名为InnerClass的内部类，在编译成功后，会出现这样两个class文件：OuterClass.class和OuterClass$InnerClass.class。

1. 内部类可以用多个实例，每个实例都有自己的状态信息，并且与其他外围对象的信息相互独立。
2. 在单个外围类中，可以让多个内部类以不同的方式实现同一个接口，或者继承同一个类。
3. 创建内部类对象的时刻并不依赖于外围类对象的创建。
4. 内部类并没有令人迷惑的“is-a”关系，他就是一个独立的实体。
5. 内部类提供了更好的封装，除了该外围类，其他类都不能访问。

静态内部类

定义在类内部的静态类，就是静态内部类。

1
2
3
4

java复制代码public class Test{
    public static class TestOne{
    }
}

1. 静态内部类可以访问外部类所有的静态变量和方法，即使是 private 的也一样。
2. 静态内部类和一般类一致，可以定义静态变量、方法，构造方法等。
3. 其它类使用静态内部类需要使用“外部类.静态内部类”方式
4. Java集合类HashMap内部就有一个静态内部类Entry。Entry是HashMap存放元素的抽象，HashMap 内部维护 Entry 数组用了存放元素，但是 Entry 对使用者是透明的。像这种和外部类关系密切的，且不依赖外部类实例的，都可以使用静态内部类

成员内部类

定义在类内部的非静态类，就是成员内部类。成员内部类不能定义静态方法和变量（final 修饰的除外）。这是因为成员内部类是非静态的，类初始化的时候先初始化静态成员，如果允许成员内部类定义静态变量，那么成员内部类的静态变量初始化顺序是有歧义的。

注意

1. 成员内部类中不能存在任何static的变量和方法
2. 成员内部类是依附于外围类的，所以只有先创建了外围类才能够创建内部类。

1
2
3
4

java复制代码public class Test{
    public class TestOne{
    }
}

局部内部类

定义在方法中的类，就是局部类。如果一个类只在某个方法中使用，则可以考虑使用局部类；

局部内部类和成员内部类一样被编译，只是它的作用域发生了改变，它只能在该方法和属性中被使用，出了该方法和属性就会失效

1
2
3
4
5
6

java复制代码public class Test{
    public void get(){
        class GetTest{
        }
    }
}

匿名内部类

匿名内部类我们必须要继承一个父类或者实现一个接口，当然也仅能只继承一个父类或者实现一个接口。同时它也是没有class关键字，这是因为匿名内部类是直接使用new来生成一个对象的引用

注意

1. 匿名内部类是没有访问修饰符的。
2. new 匿名内部类，这个类首先是要存在的。如果我们将那个InnerClass接口注释掉，就会出现编译出错
3. 注意getInnerClass()方法的形参，第一个形参是用final修饰的，而第二个却没有。同时我们也发现第二个形参在匿名内部类中没有使用过，所以当所在方法的形参需要被匿名内部类使用，那么这个形参就必须为final
4. 匿名内部类是没有构造方法的。因为它连名字都没有何来构造方法。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

简介： 今年双11，阿里云数据库技术有什么不一样？

2021年，是阿里巴巴首个100%云上双11

双11峰值计算成本

相比去年下降50%

作为全球规模最大的数字工程之一

双11无疑是对阿里技术人的“大考”

在又一次技术“严考”面前

阿里云数据库团队再次递交了诚意满满的年度答卷

在双11背后，凝聚着无数同学努力的身影

为所有奋战在前线的数据库小伙伴们打Call！

除了保障稳定顺滑的基本盘

今年，阿里云数据库全面云原生化

持续通过技术创新赋能用户

为消费者和商家提供了全方位升级的购物体验

引领技术发展路径

每一笔不起眼的订单背后

都需要强大的技术支撑

今年双11，阿里云数据库有哪些不一样的硬核技术？

让我们一起看看完整版成绩单吧！

原文链接

本文为阿里云原创内容，未经允许不得转载。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

高级架构师编程界的小學生，将在小册《Hello，分布式锁》中，带你从 0 到 1 彻底搞懂分布式锁。

🎙️作者介绍

编程界的小學生，高级架构师。

曾先后任职于北京百度移信、跟谁学。参与过百万/千万级高并发 C 端系统的设计与研发以及基础架构工作，主导了 RocketMQ 的延迟消息使其支持自定义时长的延迟级别、Eureka 的无损发布，以及 Sentinel 限流支持针对不同接口调用做不同限制等二开工作。

🤔️为什么学习分布式锁？

当今属于互联网时代，而不是传统时代，互联网项目现在大多都是分布式、集群部署，因为这样能大幅度提升业务的并发能力，但是分布式也会带来一些新的问题，比如：分布式锁、分布式事务、分布式 ID 等诸如此类的问题。

那为什么要学习分布式锁呢？

首先它是当前互联网项目必备的基础核心技术之一，其次它也是面试中常被问到的一种面试题型。比如，你是否还遇到过以下令人头秃的问题：

• 电商平台搞促销，并发流量很大，结果库存超卖了。

• 用户拉新，搞了个注册用户进行抽奖的系统，奖品是 iPhone13 Pro 且奖品数量就一个，但是多个人同时都抽到了，那不就亏钱了吗？

• 公司没有分布式调度系统，但是要执行定时任务，部署集群后，结果集群内的每台机器都执行了这个定时任务，重复执行了。

• ……

这些问题在当今互联网时代很常见了，但是我们怎么去解决呢？有的从业人员可能知道用分布式锁去解决，那么用哪一种分布式锁呢？性能和安全方面是怎样的？……一系列黑盒问题扑面而来。

而这些问题，正是《Hello，分布式锁》这本小册需要解决的。

💡 常见的学习痛点及小册亮点

其实，你去网上用“分布式锁”这几个字搜索的话，能搜到数不胜数的文章，但是，去网上搜过的从业人员应该都知道一点，那就是：网上都只是告诉你分布式锁的 API，该如何用，但是并不会介绍正确的使用姿势、有哪几种实现方式，以及各有什么利弊。或许有那种系列文章，从 0 开始讲分布式锁，一直到源码级别，但是优秀的文章真的很少，大多都是个人笔记，而不是文章，为什么这么说？因为几乎 90% 的文章都是直接贴出源码，写好注释，好一点的文章会配上图。这些其实很难读懂，即使读懂了也是理解了源码的流程，仅此而已。

那我们这个小册的亮点在哪里呢？

本小册会从 0 到 1 开始剖析分布式锁 ，但是并不会一上来就进行源码剖析，而是会采取“如何设计一把分布式锁？”这种推导式的教学方式 ，带着你先学习其中的设计思想。比如，要设计一个分布式读写锁，那本小册会带着你分析采取哪种数据结构来存储、读写互斥怎么做、读读共享怎么做等需求来一步步地推导出完整的设计思想，最后再带着我们这套设计思想去深入到开源框架的源码中去验证是不是这么实现的。

设计思想是源码的需求。需求不懂，怎么开发？ 擒贼先擒王，王（需求）搞定了，下面的小兵（源码）很容易攻破 。

🏆 通过本小册你会学到什么

本小册主要有三大核心模块：基础篇、核心篇、进阶篇。另外，还会有个补充篇模块作为扩展。

• 你可以从基础篇学习到什么是锁、什么又是分布式锁以及实现分布式锁的核心原理。

• 掌握了分布式锁的基础后，来到核心篇，在核心篇你将学到 Redis 和 ZooKeeper 实现分布式锁的全部设计思想以及核心源码，当然也会剖析面试常问的 WatchDog 实现原理等。

• 最后在进阶篇会手把手带着你去分析如何设计一些高级锁，比如分布式公平锁/非公平锁、分布式读写锁、红锁等核心设计思想以及源码。

整个知识体系你可以参考下面的知识导图👇：

因此，通过本小册你会有以下收获：

• 分布式锁到底是什么以及每种实现方式的利弊；

• Redis 实现分布式锁的核心设计思想以及源码；

• ZooKeeper 实现分布式锁的核心设计思想以及源码；

• 分布式公平锁/非公平锁、分布式读写锁、红锁的设计思想以及源码；

• 对分布式锁不再陌生，你也能手写一把高级分布式锁。

最后，我想说，如果你有互联网项目经验，知道什么是分布式锁但不知道其实现原理，或者用过分布式锁，但是想全面系统性地学习分布式锁的设计核心原理以及核心实现源码，又或者想手写一些高级锁但是不知道从何下手，都可以加入我们本小册的学习。

我非常期待你的加入，期待和你一起携手并进🤝，乘长风，破万里浪🌊，踏上分布式锁的旅途⛵️。

上新优惠 5 折，限时 14.95元，戳链接即可购买：sourl.co/fynt9p

👇也可以戳下方海报或者扫描海报二维码，即可永久解锁～快点加入学习吧～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

先上链接casbin官网

casbin能做什么？

• 支持多种编程语言Go/Java/Node/PHP/Python/.NET/Rust，一次学习多处运用
• 支持自定义请求格式，默认格式(subject,object,action)
• 具有访问控制模型model和策略policy两个核心概念
• 支持RBAC中的多层继承，不仅subject有角色，object也可以有角色
• 支持内置的超级用户，例如root或admin，超级用户可以执行任何操作而无需显式的权限声明
• 支持多种内置的操作符，如 keyMatch，方便对路径式的资源进行管理，如 /foo/bar 可以映射到 /foo*

Casbin 不能做什么？

• 身份认证 authentication（即验证用户的用户名、密码），casbin只负责访问控制。应该有其他专门的组件负责身份认证，然后由casbin进行访问控制，二者是相互配合的关系。
• 管理用户列表或角色列表。 Casbin 认为由项目自身来管理用户、角色列表更为合适， 用户通常有他们的密码，但是 Casbin 的设计思想并不是把它作为一个存储密码的容器。 而是存储RBAC方案中用户和角色之间的映射关系

快速开始

Casbin使用配置文件来设置访问控制模式。

它有两个配置文件，model.conf和policy.csv。 其中，model.conf存储了访问模型，policy.csv存储了特定的用户权限配置。 Casbin的使用非常精炼。 基本上，我们只需要一个主要结构：enforcer。 当构建这个结构时，model.conf和policy.csv将被加载

1
2

bash复制代码mkdir demo && cd demo && go mod init github.com/51op/go-sdk-demo
go get github.com/casbin/casbin/v2

• 创建model模型文件model.conf

1
2
3
4
5
6
7
8

ini复制代码[request_definition]
r = sub, obj, act
[policy_definition]
p = sub, obj, act
[matchers]
m =  r.sub == p.sub && r.obj == p.obj && r.act == p.act || r.sub == "root" #只要访问主体是root一律放行。
[policy_effect]
e = some(where (p.eft == allow))

上面模型文件规定了权限由sub,obj,act三要素组成，只有在策略列表中有和它完全相同的策略时，该请求才能通过。匹配器的结果可以通过p.eft获取，some(where (p.eft == allow))表示只要有一条策略允许即可

• 创建策略控制文件policy.csv

1
2
3
4

bash复制代码p, demo , /user, write #demo用户对/user有write权限
p, demo , /order, read #demo用户对/order有read权限
p, demo1 , /user/userlist,read #demo1用户对/user/userlist有read权限
p, demo2 , /order/orderlist,read #demo2用户对/order/orderlist有read权限

• 检查权限

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

go复制代码import (
	"fmt"
	"github.com/casbin/casbin/v2"
	gormadapter "github.com/casbin/gorm-adapter/v3"
	_ "github.com/go-sql-driver/mysql"
	"log"
	"testing"
)
func CheckPermi(e *casbin.Enforcer ,sub,obj,act string)  {
	ok, err := e.Enforce(sub, obj, act)
	if err != nil {
		return
	}
	if ok == true {
		fmt.Printf("%s CAN %s %s\n", sub, act, obj)

	} else {
		fmt.Printf("%s CANNOT %s %s\n", sub, act, obj)
	}
}
func TestCasBin( t *testing.T)  {
	e, err := casbin.NewEnforcer("./model.conf", "./policy.csv")
	if err !=nil{
		log.Fatalf("NewEnforecer failed:%v\n", err)
	}

	//基本权限设置
	CheckPermi(e, "demo", "/user", "read")
	CheckPermi(e, "demo", "/order", "write")
	CheckPermi(e, "demo1", "/user/userlist", "read")
	CheckPermi(e, "demo1", "/order/orderlist", "write")
}

可通过官网的编辑器直接运行查看结果，【直达链接】

实战项目 参考

有些代码未做抽取勿喷

• 目录结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

go复制代码dnspod/
├── api
│   ├── casbiniapi.go
│   ├── internal
│   │   └── model
│   │       └── casbin.go
├── config
│   ├── config.json
│   ├── config.yaml
│   └── model.conf
├── common
│   ├── global.go
├── Dockerfile
├── docs
│   ├── docs.go
│   ├── swagger.json
│   └── swagger.yaml
├── go.mod
├── go.sum
├── main.go
├── router
│   ├── handler
│   │   └── func.go
│   └── route.go

• 首先在configs目录下创建model.conf`文件，写入如下代码：

1
2
3
4
5
6
7
8
9
10
11

ini复制代码#此文件存储访问模型
[request_definition]
r = sub, obj, act
[policy_definition]
p = sub, obj, act
[role_definition]
g = _, _
[policy_effect]
e = some(where (p.eft == allow))
[matchers]
m = r.sub == p.sub &&  r.obj == p.obj || ParamsMatch(r.obj,p.obj) && r.act == p.act

• 在api/internal/model目录下，创建casbin.go文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

go复制代码package model
import (
	"dnspod/common"
	_ "dnspod/common"
	"log"
)
type CasinoModel struct {
	PType string `gorm:"column:p_type" json:"p_type" form:"p_type" description:"策略类型"`
	RoleId string `gorm:"column:v0" json:"role_id" form:"v0" description:"角色id"`
	Path string `gorm:"column:v1" json:"path" form:"v1" description:"api路径"`
	Method string `gorm:"column:v2" json:"method" form:"v2" description:"方法"`
}
func(c *CasinoModel) TableName()  string {
	return "casbin_rule"
}
func ( c *CasinoModel) AddPolicy() error  {

        if ok,_:=common.CasBin.AddPolicy(c.RoleId,c.Path,c.Method);ok==false{
           return  common.JsonResponse(100,"增加策略失败")
        }

        return  common.JsonResponse(200,"增加策略成功")

}

• 在common/目录下的global.go文件中增加如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Go复制代码func InitCasbinDB() *casbin.Enforcer  {
	
        dsn:=fmt.Sprintf("%s:%s@tcp(%s)/",cfg.MySQL.Username,cfg.MySQL.Password,cfg.MySQL.Host)
        adapter, _ := gormadapter.NewAdapter("mysql", dsn,)
	CasBin, _ = casbin.NewEnforcer(cfg.CasBin.FilePath, adapter)
	CasBin.AddFunction("ParamsMatch",ParamsMatchFunc)
	CasBin.LoadPolicy()
	return  CasBin
}
func ParamsMatch(fullNameKey1 string,key2 string) bool  {
	key1 := strings.Split(fullNameKey1, "?")[0]
	return util.KeyMatch2(key1,key2)
}
//注册func到casbin
func ParamsMatchFunc(args ...interface{})(interface{},error)  {
	name1 := args[0].(string)
	name2 := args[1].(string)
	return ParamsMatch(name1, name2), nil
}

• 在router/下的route.go增加请求

1
2
3
4
5
6

go复制代码  common.InitCasbinDB() //初始化 InitCasbinDB
   //Casbin权限认证
	authGroup:=router.Group("/api/v1/auth")
	{
		authGroup.POST("/addPolicy",handler.AddPolicy)
	}

• router/handler目录下的func.go中增加AddPolicy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

go复制代码//Casbin 权限管理

type CasbinInfo struct {
	Path   string `json:"path" form:"path"`
	Method string `json:"method" form:"method"`
}
type CasbinCreateRequest struct {
	RoleId      string       `json:"role_id" form:"role_id" description:"角色ID"`
	CasbinInfos []CasbinInfo `json:"casbin_infos" description:"权限模型列表"`
}
func AddPolicy(c *gin.Context ) {
	log.Printf("==========")
	var params CasbinCreateRequest
	c.ShouldBind(&params)

	for _, v := range params.CasbinInfos {

		log.Println(params.RoleId, v.Path, v.Method)
		err := api.AddPolicyApi(params.RoleId, v.Path, v.Method)
		if err != nil {
		//	c.JSON(http.StatusOK,gin.H{
		//		"res":"bad",
		//	})
		}
	}
	 c.JSON(http.StatusOK,gin.H{
		"res":"ok",
	})
}

• 在api/目录下创建casbiniapi.go文件

1
2
3
4
5
6
7
8
9
10
11
12

go复制代码package api
import "dnspod/api/internal/model"
func AddPolicyApi(roleId string, path, method string)  error {
	p:=model.CasinoModel{
		PType: "p",
		RoleId: roleId,
		Path: path,
		Method: method,
	}
	p.AddPolicy()
	return nil
}

最后启动项目

验证

查看mysql库里数据就有了

• 权限验证通过后处理正常业务逻辑

增加访问入口

1
2

go复制代码
authGroup.GET("/testPolicy",common.CasbinMiddleware(),handler.TestListPolicics)

测试业务逻辑

1
2
3
4

go复制代码func TestListPolicics(c *gin.Context)  {

	c.JSON(http.StatusOK,common.Reponse{200,"权限通过正常的业务逻辑",""})
}

增加casbin中间件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

go复制代码//casbin中间件
func CasbinMiddleware() gin.HandlerFunc  {
	return func(c *gin.Context) {
		r:=NewResponseContext(c)
		path:=c.Request.URL.RequestURI() //
		method:=c.Request.Method
		log.Println(path,method)
		//验证url权限
		roleId:="admin"
		ok, _ := CasBin.Enforce(roleId, path, method)
		if ok {
			c.Next()
		}else {
			c.Abort()
			r.ResponseContextMsg("很遗憾,权限验证没有通过")
			return
		}
	}
}

在当前mysql库中没有 p /api/v1/auth/testPolicy GET策略的时候执行这个api会返回没有权限

添加api/v1/auth/addPolicy权限

然后在执行/api/v1/auth/testPolicy 这个接口已经有权限了

• 查询角色下的权限

1

go复制代码authGroup.POST("/listPolicy",handler.GetListPolicy) //获取当前用户下的所有策略

1
2
3
4
5
6
7
8

go复制代码
func GetListPolicy( c *gin.Context)  {
	params:=CasbinRequestRoleId{}
	c.ShouldBind(&params)
	res:=api.ListPolicyApiByRoleId(params.RoleId)
	log.Println(res)
	c.JSON(http.StatusOK,common.Reponse{200,"获取成功",res})
}

1
2
3
4
5

go复制代码
func ListPolicyApiByRoleId(roleId string)  [][]string {
	r:=model.CasinoModel{RoleId: roleId}
	return  r.ListPolicyByRoleId(roleId)
}

基于RBAC权限认证

model模型中要修匹配器如下:

1
2
3

go复制代码//使用keyMatch函数，这种情况下才能匹配传递不通参数的用户来匹配不同用户的权限,/api/v1/auth/testPolicy/user1、/api/v1/auth/testPolicy/user2
[matchers]
m = g(r.sub, p.sub) && keyMatch(r.obj, p.obj)  && r.act == p.act

• 增加角色

分为给用户分配单一角色、给用户分配多个角色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

go复制代码//给单一用户分配单一角色
func (c *CasinoModel) AddRoleForUser(user string,roles string) error {
	if ok, _ := common.CasBin.AddRoleForUser(user, roles);!ok{
		return errors.New("给用户分配单一角色失败")
	}
	return nil
}

//给单一用户分配多个角色
func (c *CasinoModel) AddRolesForUser(user string,roles []string)  error {
	if ok, _ := common.CasBin.AddRolesForUser(user, roles);!ok{
		return errors.New("数据库中已经对应的roles策略")
	}
	return nil
}

在目录./router/handler/func.go中增加路由

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

go复制代码type UserRoleInfo struct {
	UserName string `json:"user_name"`
	RoleName string `json:"role_name"`
}
func AddRoleUser(c *gin.Context)  {
	u:= UserRoleInfo{}
	c.ShouldBind(&u)
	if err:=api.AddRoleForUserApi(u.UserName,u.RoleName);err !=nil{
		common.ErrorResp(c,http.StatusInternalServerError,"给用户增加role失败")
		return
	}
	common.SuccessResp(c,"给用户增加role成功")

}
//给单一用户分配多个角色
type RolesInfoRequest struct {
	UserName string `json:"user_name"`
	RoleName []string `json:"role_name"`
}
func AddRolesUser(c *gin.Context)  {
	ro:= RolesInfoRequest{}
	err:=c.ShouldBind(&ro)
	if err !=nil {
		panic(err)
	}
	if err:=api.AddRolesForUserApi(ro.UserName,ro.RoleName);err!=nil{
		common.ErrorResp(c,http.StatusInternalServerError,"给用户分配多个roles失败")
		return
	}
	common.SuccessResp(c,"给用户分配多个roles成功")
}

router/route.go中增加路由

1
2

go复制代码        authGroup.POST("/AddRoleUser",handler.AddRoleUser)
		authGroup.POST("/AddRolesUser",handler.AddRolesUser)

• 验证RBAC

查看数据库，就有了相对应的一条记录

• 给角色member分配测试uri的权限

查看数据库已有相对应的记录

分别请求/api/v1/auth/testPolicy/user1和/api/v1/auth/testPolicy/user2

user1验证未通过

user2通过

【关注我】持续更新ing。。。。。。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

「这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战」。

  温馨提示: 本文总共800字,阅读完大概需要1-3分钟,希望阅读本文能够对您有所帮助,如果阅读过程中有什么好的建议、看法,欢迎在文章下方留言或者私信我,您的意见对我非常宝贵,再次感谢你阅读本文。

一: Restful API展示

  废话不多说、先展示Restful 风格的API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

java复制代码1、// 新增一篇文章
@RequestMapping(value = "/articles",method = RequestMethod.POST)

2、// 删除一篇文章
@RequestMapping(value = "/articles",method = RequestMethod.DELETE)

3、// 删除某一类文章下的一篇文章
@RequestMapping(value = "/types/{id}/articles",method = RequestMethod.DELETE)

4、 // 查询一篇文章
@RequestMapping(value = "/articles/{id}",method = RequestMethod.GET)

5、// 查询某一类文章中的所有文章
@RequestMapping(value = "/types/{id}/articles",method = RequestMethod.GET)

6、// 修改一篇文章(全部属性)
@RequestMapping(value = "/articles/{id}",method = RequestMethod.PUT)

7、// 修改一篇文章(某些属性)
@RequestMapping(value = "/articles/{id}",method = RequestMethod.PATCH)

二: Restful API风格的由来

  Rest(Representational State Transfer)全称是表述性状态转移,它是由Roy Thomas Fielding博士在2000年提出的,它表示的是一种新的架构风格，一种轻量级,跨平台,跨语言的架构设计。

  API(Application Programming Interface): 既我们熟知的接口,是一组编程接口规范、客户端与服务端通过请求响应进行数据通信。

  RestfulAPI: 它不是一种新的技术,而是基于Rest架构思想的API设计风格。

三: Restful API风格的优点

(一) 优点:

1. 它是面向资源的(名词)
2. 通过URL就知道需要什么资源
3. 通过Http Method(get/post…)就知道针对资源干什么
4. 通过Http Status Code就知道结果如何

(二) 优点解释:

  (1)通过URL就知道需要什么资源：表示Restful风格的API可以直接通过URL就可以看到需要操作的是什么资源,有语义化。

  (2)Restful风格的API是面向资源(名称)的,既URL中不会带相应的动词,针对资源的操作是通过Http Method(既:post-增、delete-删、put-改(一般是提供实体的全部信息)、patch-改(修改实体的某些属性)、get-查)来实现的。

  (3)通过Http Status Code就知道结果如何: 如常见的200(成功)、400(错误的请求参数)、500(服务器错误)等。

四: Restful API风格的注意事项

1. 请求资源应该使用复数而不是单数,因为Restful API风格是是面向资源的(名词)
2. 强制性添加API版本声明，不要发布无版本的API,如: api.v1/blogs(开闭原则)，对拓展开发、对修改关闭,如果后面需要添加新的功能，可以直接新开接口加上版本号就可。

五: 总结

   无论是面试或者工作中,总会听到别人问到关于Restful风格API的问题,其实,它并不是我们想象中的那么高深莫测,它只是一种设置API架构风格,而不是一种新的技术,遵循这种风格设计的API就被称为Restful API。

  相信，看完这篇文章，你已经对Restful API有了一个新的认识,如果还有什么问题需要反馈的,可以在下方留言或者私信我,我看到会第一时间回复,如果你觉得文字对你有帮助,麻烦给我一个点赞和关注,后面会给大家分享更多技术知识,最后,感谢你的阅读,如果能够帮助到你,那是我最大的收获。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

「这是我参与11月更文挑战的第 18 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

输出二叉树的右视图

题目来源：LeetCode-199. 二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

示例

示例 1

1
2

csharp复制代码输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2

1
2

ini复制代码输入: [1,null,3]
输出: [1,3]

示例 3

1
2

ini复制代码输入: []
输出: []

提示：

• 二叉树的节点个数的范围是 [0,100]
• 100 <= Node.val <= 100

解题

解法一：深度优先搜索

思路

本题最容易想到的思路就是，如果我能遍历每一层，然后输出每一层的最右边的结点就可以了。我们知道，二叉树的层序遍历，需要借助队列来实现。实现的过程中发现，我们没法记录队列中的结点当前属于哪一层，因此这个方法其实是行不通的

那换一种思路，用深度优先搜索，如果对于树的每一层，我都先访问它的右子树，那么每一层我们访问到的第一个节点，一定是最右边的那个节点（假设右节点是存在的）

深度优先搜索：随意选择一个岔路口来走，走着走着发现走不通的时候，就回退到上一个岔路口，重新选择一条路继续走，直到走完所有的情况

通过上边的方式，我们就可以记录每一层访问的第一个节点，等搜索完所有的层，就得到了我们想要的结果（深度优先搜索，我们通常是用栈来实现）。你可能有个思路，但是并不是很明白，画图是最好的方式，用图来展示整个过程

有了思路，代码还算比较好写，需要借助两个栈

nodeStack：用来记录每次遍历到的节点（入栈的时候，右子树后进，这样访问栈的时候，每一层第一个出来的，一定是右子树（假设右子树存在）） depthStack：记录树的深度，目的是为了知道，每一层是否已经有我们需要的结点了，如果已经有了，该层的剩余结点就不需要了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

go复制代码//输出二叉树的右视图
//深度优先搜索实现
func rightSideView(root *TreeNode) []int {
	rightViewMap := map[int]int{} //记录每一层第一个访问到的节点值（用map是为了知道每一层是否已经有访问过的结点）
	rightView := []int{} //最终存右视图结果的
	nodeStack := []*TreeNode{}
	depthStack := []int{}
	maxDepth := -1 //记录最大深度是为了最后变量右视图

	nodeStack = append(nodeStack, root) //根节点入栈
	depthStack = append(depthStack, 0) //跟结点属于第0层
	for len(nodeStack) != 0 {
		node := nodeStack[len(nodeStack)-1] //取出栈顶元素
		nodeStack = nodeStack[:len(nodeStack)-1]

		currDepth := depthStack[len(depthStack)-1] //当前节点属于哪一层
		depthStack = depthStack[:len(depthStack)-1]

		if node != nil {
			//维护二叉树的最大深度
			if currDepth > maxDepth {
				maxDepth = currDepth
			}
			
			//判断当前层，是否已经有节点被记录了.如果没有，才记录下来
			if _, ok := rightViewMap[currDepth];!ok {
				rightViewMap[currDepth] = node.Val
			}

			nodeStack = append(nodeStack, node.Left)
			nodeStack = append(nodeStack, node.Right)//右节点后入栈（后进先出）
			depthStack = append(depthStack, currDepth+1) //新进入的这两个结点的层数是相同的
			depthStack = append(depthStack, currDepth+1)
		}
	}
	for i:=0; i <= maxDepth; i++ {
		rightView = append(rightView, rightViewMap[i])
	}

	return rightView
}

解法二：广度优先搜索

思路

广度优先搜索：是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索

如果理解了上边的深度优先的解法，用广度优先来解决就很简单了。我首先知道的是，用广度优先搜索，需要借助队列来实现，队列的夜店是先进先出，所以我们在搜索树的时候，可以让左子树先进队列，右子树后进，这样我们在访问每一层的结点的时候，不断更新我们需要的值，每一层最后一个访问到的，一定就是右子树

思路和上边一样，需要维护两个队列，一个记录结点，一个记录层。如果你看懂了上边的代码，下边这个代码，一看就明白

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

ini复制代码func rightSideView2(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	rightViewMap := map[int]int{}
	rightView := []int{}
	maxDepth := 0

	nodeQueue := []*TreeNode{root}
	depthQueue := []int{}
	depthQueue = append(depthQueue, 0)

	for len(nodeQueue) != 0 {
		node := nodeQueue[0]
		if len(nodeQueue) <= 1 {
			nodeQueue = []*TreeNode{}
		} else {
			nodeQueue = nodeQueue[1:]
		}

		currDepth := depthQueue[0]
		if len(depthQueue) <= 1 {
			depthQueue = []int{}
		} else {
			depthQueue = depthQueue[1:]
		}

		if node != nil {
			if currDepth > maxDepth {
				maxDepth = currDepth
			}
			rightViewMap[currDepth] = node.Val

			nodeQueue = append(nodeQueue, node.Left)
			nodeQueue = append(nodeQueue, node.Right)
			depthQueue = append(depthQueue, currDepth+1)
			depthQueue = append(depthQueue, currDepth+1)
		}
	}

	for i := 0; i <= maxDepth; i++ {
		rightView = append(rightView, rightViewMap[i])
	}

	return rightView
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

声明：本文只作学习研究，禁止用于非法用途，否则后果自负，如有侵权，请告知删除，谢谢！

前言

这次搞搞小程序的，来篇干货吧，具体小程序名称就不说了，主要是写下逆向的思路方法

一、请求分析

这里随便输入车牌号，然后抓请求

请求头中的s参数，就是我们要解决的

这里是请求得参数，加密过程可能会用到

二、获取参数

接下来就是获取小程序源码包，然后用工具进行反编译，这部分我就不详细说了，百度上找有很多。

然后打开微信开发者工具，相当于我们的浏览器，在此环境上找出加密的位置。

由于本地小程序是没有网的，所以无法直接进栈查找参数，只能从加密逻辑上分析，在进行部分关键词的搜索。

一般小程序的加密参数都是一些请求参数的组成在加上盐的MD5，所以先搜下md5这个参数。

搜到的js文件不多，一个一个看过去，然后在这里找到了可疑几个方法。

然后就是继续搜索这几个方法在哪里调用的，先看看secondMD5Validate，最后搜出来只有这两位置，所以这个方法并没有给我们带来信息。

然后搜firstMD5Validate，搜出来三个，同名的只有两个，跟上面的方法一样，没得到啥信息。

接着搜第三个，除去方法定义后，只有在一个位置调用了。

这里就很关键了，我们看到了他传入的是f.carNumber，而这个carNumber大概就是我们输入的车牌号了，而且这个f有正是我们传入的那几个参数，因为参数名称都一样，所以大概率可以判断出这个l的值就是我们需要的s值。

这里我们就来证实下，继续往下看这个，l在这个被传入，我们搜索下GET_PARKINNG_FEE。

找到了他请求得接口，正好是我们抓包的链接。

到此，我们只需要解决Object(s.getSignObject)这个方法的作用就ok了。

然后分析下这个函数里面做了啥操作。

这个t 取得是传入参数的第一个，而传入参数我们知道了，就是carNumber，所以这个t=carNumber。

e是字符串数组。

n这玩意取得是时间戳。

然后我们又从返回的这个{t: n,s: o(n + t + e[n % e.length])}字典，又验证了我们找的加密位置是正确的。

就看这个s，o方法，传入n + t + e[n % e.length]，这个参数看的明白，再解决o函数。

o函数是下面这个，多的不说，一看就像MD5。

知道参数跟加密方法后，我们直接开始验证一开始抓的那个包，然后发现是一致的，到此我们就成功了。

三、请求测试

整个流程下来，花点时间，再结合一些经验，应该是不难的！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战

过滤

过滤的安装

过滤功能不是django rest_framwork内置的，需要安装第三方的包

pip install django-filter

注意：django-filter只能运行在django2.2版本及以上，如果你的电脑上装的django版本低于2.2版本，在安装django-filter的时候，会自动卸载电脑上的django重新安装最新版本的django及django-filter

过滤的基本使用

过滤就是在获取到全部信息的前提下对结果进行过滤,因此视图类只需要实现获取全部数据的功能即可，即视图类继承ListAPIView即可。

过滤的方式是在路由 ?字段=过滤条件

注意：

只有继承了GenericAPIView或者其他继承了GenericAPIView的子类或者需要搭配GenericAPIView的扩展类使用过滤才会有效果。如果自己在视图类中定义了获取所有数据的方法，由于内部没有filter_queryset方法就会导致filter不起作用。

• 需要注册应用

1
2
3
4

python复制代码INSTALLED_APPS = [
    ...
    'django_filters',  # 需要注册应用，
]

• 全局配置/局部配置

1
2
3
4
5
6
7
8
9

python复制代码# 全局配置
REST_FRAMEWORK = {
    ...
    'DEFAULT_FILTER_BACKENDS': ('django_filters.rest_framework.DjangoFilterBackend',)
}

# 局部配置
from django_filters.rest_framework import DjangoFilterBackend
filter_backends = [DjangoFilterBackend,]

• 在视图中添加filter_fields属性，指定可以过滤的字段

1
2
3
4
5
6

python复制代码class StudentListView(ListAPIView):
    queryset = Student.objects.all()
    serializer_class = StudentSerializer
    filter_fields = ('age', 'sex')

# 127.0.0.1:8000/four/students/?sex=1

代码实例

• 全局配置

1

python复制代码'DEFAULT_FILTER_BACKENDS': ['django_filters.rest_framework.DjangoFilterBackend'],

• 视图类

1
2
3
4
5

python复制代码from rest_framework.generics import ListAPIView
class BookView(ListAPIView):
    queryset = models.Book.objects.all()
    serializer_class = BookModelSerializer
    filter_fields = ('name','price')

排序

对于列表数据，REST framework提供了OrderingFilter过滤器来帮助我们快速指明数据按照指定字段进行排序。

使用方法：

在类视图中设置filter_backends，使用rest_framework.filters.OrderingFilter过滤器，REST framework会在请求的查询字符串参数中检查是否包含了ordering参数，如果包含了ordering参数，则按照ordering参数指明的排序字段对数据集进行排序。

前端可以传递的ordering参数的可选字段值需要在ordering_fiel ds中指明。

1
2
3
4
5
6
7
8
9

python复制代码class StudentListView(ListAPIView):
    queryset = Student.objects.all()
    serializer_class = StudentModelSerializer
    filter_backends = [OrderingFilter]
    ordering_fields = ('id', 'age')

# 127.0.0.1:8000/books/?ordering=-age
# -id 表示针对id字段进行倒序排序
# id  表示针对id字段进行升序排序

如果需要在过滤以后再次进行排序，则需要两者结合!

1
2
3
4
5
6
7
8
9
10
11
12
13
14

python复制代码from rest_framework.generics import ListAPIView
from students.models import Student
from .serializers import StudentModelSerializer
from django_filters.rest_framework import DjangoFilterBackend

class Student3ListView(ListAPIView):
    queryset = Student.objects.all()
    serializer_class = StudentModelSerializer
    filter_fields = ('age', 'sex')
    '''
    在局部配置排序时使用的字段与过滤一致，而局部配置会覆盖全局配置，所以需要重新声明过滤组件，否则过滤组件会失效
    '''
    filter_backends = [OrderingFilter,DjangoFilterBackend]
    ordering_fields = ('id', 'age')

结语

文章首发于微信公众号程序媛小庄，同步于掘金。

码字不易，转载请说明出处，走过路过的小伙伴们伸出可爱的小指头点个赞再走吧(╹▽╹)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

正确的创建合适的索引，是提升数据库查询性能的基础。在正式讲解之前，对后面举例中使用的表结构先简单看一下：

1
2
3
4
5
6
7
8

sql复制代码create table user
(
    id     bigint  not null comment 'id' primary key,
    name   varchar(200) null comment 'name',
    age    bigint       null comment 'age',
    gender int          null comment 'gender',
    key (name)
);

索引是什么及工作机制？

索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。其工作机制如下图：

上图中，如果现在有一条sql语句 select * from user where id = 40，如果没有索引的条件下，我们要找到这条记录，我们就需要在数据中进行全表扫描，匹配id = 13的数据。

如果有了索引，我们就可以通过索引进行快速查找，如上图中，可以先在索引中通过id = 40进行二分查找，再根据定位到的地址取出对应的行数据。

MySQL数据库为什么要使用B+TREE作为索引的数据结构？

二叉树为什么不可行

对数据的加速检索，首先想到的就是二叉树，二叉树的查找时间复杂度可以达到O(log2(n))。下面看一下二叉树的存储结构：

二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率，但是它有一个问题：二叉树以第一个插入的数据作为根节点，如上图中，如果只看右侧，就会发现，就是一个线性链表结构。如果我们现在的数据只包含1, 2, 3, 4，就会出现

以下情况：

如果我们要查询的数据为4，则需要遍历所有的节点才能找到4，即，相当于全表扫描，就是由于存在这种问题，所以二叉查找树不适合用于作为索引的数据结构。

平衡二叉树为什么不可行

为了解决二叉树存在线性链表的问题，会想到用平衡二叉查找树来解决。下面看看平衡二叉树是怎样的：

图

平衡二叉查找树定义为：节点的子节点高度差不能超过1,如上图中的节点20，左节点高度为1，右节点高度0，差为1，所以上图没有违反定义，它就是一个平衡二叉树。保证二叉树平衡的方式为左旋，右旋等操作，至于如何左旋右旋，可以自行去搜索相关的知识。

如果上图中平衡二叉树保存的是id索引，现在要查找id = 8的数据，过程如下：

1、把根节点加载进内存，用8和10进行比较，发现8比10小，继续加载10的左子树。

2、把5加载进内存，用8和5比较，同理，加载5节点的右子树。

3、此时发现命中，则读取id为8的索引对应的数据。

索引保存数据的方式一般有两种：

• 数据区保存id 对应行数据的所有数据具体内容。
• 数据区保存的是真正保存数据的磁盘地址。

到这里，平衡二叉树解决了存在线性链表的问题，数据查询的效率好像也还可以，基本能达到O(log2(n))， 那为什么mysql不选择平衡二叉树作为索引存储结构，他又存在什么样的问题呢？

1、搜索效率不足。一般来说，在树结构中，数据所处的深度，决定了搜索时的IO次数（MySql中将每个节点大小设置为一页大小，一次IO读取一页 / 一个节点）。如上图中搜索id = 8的数据，需要进行3次IO。当数据量到达几百万的时候，树的高度就会很恐怖。

2、查询不不稳定。如果查询的数据落在根节点，只需要一次IO，如果是叶子节点或者是支节点，会需要多次IO才可以。

3、存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO的预读能力。因为操作系统和磁盘之间一次数据交换是以页为单位的，一页大小为 4K，即每次IO操作系统会将4K数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K的内容。幸幸苦苦做了一次的IO操作，却只加载了一个关键字。在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次的IO。

那有没有一种结构能够解决二叉树的这种问题呢？有，那就是多路平衡查找树。

多路平衡查找树(Balance Tree)

B Tree 是一个绝对平衡树，所有的叶子节点在同一高度，如下图所示：

上图为一个2-3树（每个节点存储2个关键字，有3路），多路平衡查找树也就是多叉的意思，从上图中可以看出，每个节点保存的关键字的个数和路数关系为：关键字个数 = 路数 – 1。

假设要从上图中查找id = X的数据，B TREE 搜索过程如下：

1、取出根磁盘块，加载40和60两个关键字。

2、如果X等于40，则命中；如果X小于40走P1；如果40 < X < 60走P2；如果X = 60，则命中；如果X > 60走P3。

3、根据以上规则命中后，接下来加载对应的数据， 数据区中存储的是具体的数据或者是指向数据的指针。

为什么说这种结构能够解决平衡二叉树存在的问题呢？

B Tree 能够很好的利用操作系统和磁盘的交互特性， MySQL为了很好的利用磁盘的预读能力，将页大小设置为16K，即将一个节点（磁盘块）的大小设置为16K，一次IO将一个节点（16K）内容加载进内存。这里，假设关键字类型为 int，即4字节，若每个关键字对应的数据区也为4字节，不考虑子节点引用的情况下，则上图中的每个节点大约能够存储（16 * 1000）/ 8 = 2000个关键字，共2001个路数。对于二叉树，三层高度，最多可以保存7个关键字，而对于这种有2001路的B树，三层高度能够搜索的关键字个数远远的大于二叉树。

这里顺便说一下：在B Tree保证树的平衡的过程中，每次关键字的变化，都会导致结构发生很大的变化，这个过程是特别浪费时间的，所以创建索引一定要创建合适的索引，而不是把所有的字段都创建索引，创建冗余索引只会在对数据进行新增，删除，修改时增加性能消耗。

B树确实已经很好的解决了问题，我先这里先继续看一下B+Tree结构，再来讨论BTree和B+Tree的区别。

先看看B+Tree是怎样的，B+Tree是B Tree的一个变种，在B+Tree中，B树的路数和关键字的个数的关系不再成立了，数据检索规则采用的是左闭合区间，路数和关键个数关系为1比1，具体如下图所示：

如果上图中是用ID做的索引，如果是搜索X = 1的数据，搜索规则如下：

1、取出根磁盘块，加载1，28，66三个关键字。

2、X <= 1 走P1，取出磁盘块，加载1，10，20三个关键字。

3、X <= 1 走P1，取出磁盘块，加载1，8，9三个关键字。

4、已经到达叶子节点，命中1，接下来加载对应的数据，图中数据区中存储的是具体的数据。

B TREE和B+TREE区别是什么？

1、B+Tree 关键字的搜索采用的是左闭合区间，之所以采用左闭合区间是因为他要最好的去支持自增id，这也是mysql的设计初衷。即，如果id = 1命中，会继续往下查找，直到找到叶子节点中的1。

2、B+Tree 根节点和支节点没有数据区，关键字对应的数据只保存在叶子节点中。即只有叶子节点中的关键字数据区才会保存真正的数据内容或者是内容的地址。而在B树种，如果根节点命中，则会直接返回数据。

3、在B+Tree中，叶子节点不会去保存子节点的引用。

4、B+Tree叶子节点是顺序排列的，并且相邻的节点具有顺序引用的关系，如上图中叶子节点之间有指针相连接。

MySQL为什么最终要去选择B+Tree？

1、B+Tree是B TREE的变种，B TREE能解决的问题，B+TREE也能够解决（降低树的高度，增大节点存储数据量）

2、B+Tree扫库和扫表能力更强。如果我们要根据索引去进行数据表的扫描，对B TREE进行扫描，需要把整棵树遍历一遍，而B+TREE只需要遍历他的所有叶子节点即可（叶子节点之间有引用）。

3、B+TREE磁盘读写能力更强。他的根节点和支节点不保存数据区，所以根节点和支节点同样大小的情况下，保存的关键字要比B TREE要多。而叶子节点不保存子节点引用，能用于保存更多的关键字和数据。所以，B+TREE读写一次磁盘加载的关键字比B TREE更多。

4、B+Tree排序能力更强。上面的图中可以看出，B+Tree天然具有排序功能。

5、B+Tree查询性能稳定。B+Tree数据只保存在叶子节点，每次查询数据，查询IO次数一定是稳定的。当然这个每个人的理解都不同，因为在B TREE如果根节点命中直接返回，确实效率更高。

MySQL B+Tree具体落地形式

这里主要讲解的是MySQL根据B+Tree索引结构不同的两种存储引擎（MYISAM 和 INNODB）的实现。

首先找到MySQL保存数据的文件夹，看看MySQL是如何保存数据的：

1
2
3
4
5
6

sql复制代码mysql> show variables like '%datadir%';
+---------------+------------------------+
| Variable_name | Value                  |
+---------------+------------------------+
| datadir       | /usr/local/mysql/data/ |
+---------------+------------------------+

进入到这个目录下，这个目录下保存的是所有数据库，再进入到具体的一个数据库目录下。就能够看到MySQL存储数据和索引的文件了。

这里我创建了两张表，user_innod和user_myisam，分别指定索引为innodb和myisam。对于每张表，MySQL会创建相应的文件保存数据和索引，具体如下：

1
2
3
4
5

diff复制代码-rw-rw----. 1 mysql mysql      8652 May  3 21:11 user_innodb.frm
-rw-rw----. 1 mysql mysql 109051904 May  7 21:26 user_innodb.ibd
-rw-rw----. 1 mysql mysql      8682 May 16 18:27 user_myisam.frm
-rw-rw----. 1 mysql mysql         0 May 16 18:27 user_myisam.MYD
-rw-rw----. 1 mysql mysql      1024 May 16 18:27 user_myisam.MYI

从图中可以看出：

• MYISAM存储引擎存储数据库数据，一共有三个文件：
• Frm：表的定义文件。
• MYD：数据文件，所有的数据保存在这个文件中。
• MYI：索引文件。
• Innodb存储引擎存储数据库数据，一共有两个文件(没有专门保存数据的文件)：
• Frm文件：表的定义文件。
• Ibd文件：数据和索引存储文件。数据以主键进行聚集存储，把真正的数据保存在叶子节点中。

MyISAM存储引擎

说明：为了画图简便，下面部分图使用在线数据结构工具进行组织数据，组织的B+Tree为右闭合区间，但不影响理解存储引擎数据存储结构。

在MYISAM存储引擎中，数据和索引的关系如下：

如何查找数据的呢？

如果要查询id = 40的数据：先根据MyISAM索引文件（如上图左）去找id = 40的节点，通过这个节点的数据区拿到真正保存数据的磁盘地址，再通过这个地址从MYD数据文件（如上图右）中加载对应的记录。

如果有多个索引，表现形式如下：

所以在MYISAM存储引擎中，主键索引和辅助索引是同级别的，没有主次之分。

Innodb存储引擎

Innodb主键索引为聚集索引，首先简单理解一下聚集索引的概念：数据库表行中数据的物理顺序和键值的逻辑顺序相同。

Innodb以主键索引来聚集组织数据的存储，下面看看Innodb是如何组织数据的。

如上图中，叶子节点的数据区保存的就是真实的数据，在通过索引进行检索的时候，命中叶子节点，就可以直接从叶子节点中取出行数据。mysql5.5版本之前默认采用的是MyISAM引擎，5.5之后默认采用的是innodb引擎。

在innodb中，辅助索引的格式如下图所示？

如上图，主键索引的叶子节点保存的是真正的数据。而辅助索引叶子节点的数据区保存的是主键索引关键字的值。

假如要查询name = C 的数据，其搜索过程如下：

1、先在辅助索引中通过C查询最后找到主键id = 9.

2、在主键索引中搜索id为9的数据，最终在主键索引的叶子节点中获取到真正的数据。

所以通过辅助索引进行检索，需要检索两次索引。

之所以这样设计，一个原因就是：如果和MyISAM一样在主键索引和辅助索引的叶子节点中都存放数据行指针，一旦数据发生迁移，则需要去重新组织维护所有的索引。

把Innodb 和 MYISAM区别放在一张图中看，就如下所示：

创建索引的几大原则

列的离散型

离散型的计算公式：count(distinct column_name):count(*)，就是用去重后的列值个数比个数。值在 (0,1] 范围内。离散型越高，选择型越好。

如下表中各个字段，明显能看出Id的选择性比gender更高。

1
2
3
4
5
6
7
8
9
10
11

sql复制代码mysql> select * from user;
+----+--------------+------+--------+
| id | name         | age  | gender |
+----+--------------+------+--------+
| 20 | 君莫笑       |   15 |      1 |
| 40 | 苏沐橙       |   12 |      0 |
| 50 | 张楚岚       |   25 |      1 |
| 60 | 诸葛青       |   27 |      1 |
| 61 | 若有人兮     |   38 |      0 |
| 64 | 冯宝宝       |   18 |      0 |
+----+--------------+------+--------+

为什么说离散型越高，选择型越好？

因为离散度越高，通过索引最终确定的范围越小，最终扫面的行数也就越少。

最左匹配原则

对于索引中的关键字进行对比的时候，一定是从左往右以此对比，且不可跳过。之前讲解的id都为int型数据，如果id为字符串的时候，如下图：

当进行匹配的时候，会把字符串转换成ascll码，如abc变成97 98 99，然后从左往右一个字符一个字符进行对比。所以在sql查询中使用like %a 时候索引会失效，因为%表示全匹配，如果已经全匹配就不需要索引，还不如直接全表扫描。

最少空间原则

前面已经说过，当关键字占用的空间越小，则每个节点保存的关键字个数就越多，每次加载进内存的关键字个数就越多，检索效率就越高。创建索引的关键字要尽可能占用空间小。

联合索引

• 单列索引：节点中的关键字[name]
• 联合索引：节点中的关键字[name, age]

可以把单列索引看成特殊的联合索引，联合索引的比较也是根据最左匹配原则。

联合索引列的选择原则

• 经常用的列优先（最左匹配原则）
• 离散度高的列优先（离散度高原则）
• 宽度小的列优先（最少空间原则）

实例分析

下面简单举例平时经常会遇到的问题：

如，平时经常使用的查询sql如下：

1
2

csharp复制代码select * from users where name = ?
select * from users where name = ? and age = ?

为了加快检索速度，为上面的查询sql创建索引如下：

1
2

scss复制代码create index idx_name on users(name)
create index idx_name_age on users(name, age)

在上面解决方案中，根据最左匹配原则，idx_name为冗余索引， where name = ?同样可以利用索引idx_name_age进行检索。冗余索引会增加维护B+TREE平衡时的性能消耗，并且占用磁盘空间。

覆盖索引

如果查询的列，通过索引项的信息可直接返回，则该索引称之为查询SQL的覆盖索引。覆盖索引可以提高查询的效率。

如上图，如果通过name进行数据检索：

1

csharp复制代码select * from users where name = ?

因为只需要id的值，通过name查询的时候，扫描完name索引，我们就能够获得id的值了，所以就不需要再去扫面id索引，就会直接返回。

当然，如果你同时需要获取age的值：

1

bash复制代码select id，age from users where name = ?

这样就无法使用到覆盖索引了。

知道了覆盖索引，就知道了为什么sql中要求尽量不要使用select *，要写明具体要查询的字段。其中一个原因就是在使用到覆盖索引的情况下，不需要进入到数据区，数据就能直接返回，提升了查询效率。在用不到覆盖索引的情况下，也尽可能的不要使用select *，如果行数据量特别多的情况下，可以减少数据的网络传输量。当然，这都视具体情况而定，通过select返回所有的字段，通用性会更强，一切有利必有弊。

总结

• 索引列的数据长度满足业务的情况下能少则少。
• 表中的索引并不是越多越好，冗余或者无用索引会占用磁盘空间并且会影响增删改的效率。
• Where 条件中，like 9%， like %9%， like%9，三种方式都用不到索引。后两种方式对于索引是无效的。第一种9%是不确定的，决定于列的离散型，结论上讲可以用到，如果发现离散情况特别差的情况下，查询优化器觉得走索引查询性能更差，还不如全表扫描。
• Where条件中IN可以使用索引， NOT IN 无法使用索引。
• 多用指定查询，只返回自己想要的列，少用select *。
• 查询条件中使用函数，索引将会失效，这和列的离散性有关，一旦使用到函数，函数具有不确定性。
• 联合索引中，如果不是按照索引最左列开始查找，无法使用索引。
• 对联合索引精确匹配最左前列并范围匹配另一列，可以使用到索引。
• 联合索引中，如果查询有某个列的范围查询，其右边所有的列都无法使用索引。

转自：he_321

链接：blog.csdn.net/b\_x\_p/art…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“实现函数，计算x的n次幂。”

题目链接：

来源：力扣（LeetCode）

链接：50. Pow(x, n) - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

1
2
3

ini复制代码示例 1：
输入： x = 2.00000, n = 10
输出： 1024.00000

1
2
3

ini复制代码示例 2：
输入： x = 2.10000, n = 3
输出： 9.26100

二、解题

1、思路分析

这道题可以使用快速幂+递归的方法解题。

快速幂算法，本质就是分治算法，将大问题分解成小问题，然后递归解决。

快速幂算法：

比如要计算x8，可以按照x → x2 → x4 → x8的顺序，从x开始，每次将上一次的结果进行平方，3次后就可以得到x8的结果，而不需要对x乘8次x。

如果幂是偶数，比如x9，可以按照x → x2 → x4 → x9的顺序，这些步骤中，还是按照将上一次结果平方，而在x4 → x9的步骤中，需要将上一个结果进行平方，还需要额外乘一个x。

综上所述，可以推到出规律，如果要计算xn，首先判断n的奇偶：

• n为偶数，那么xn=yn
• n为奇数，那么xn=yn * x

接着就可以递归地得到结果了。

2、代码实现

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13

csharp复制代码public class Solution {
    //递归
    public double MyPow(double x, int n) {
        return (n >= 0) ? res(x, n) : 1 / res(x, n);
    }
    private double res(double x, int n)
    {
        if(n == 0)
            return 1;
        double y = res(x, n / 2);
        return (n % 2 == 0) ? y * y :y * y * x;
    }
}

3、时间复杂度

时间复杂度 ： O(log n)

其中n为遍历的层数。

空间复杂度： O(log n)

其中n为遍历的层数。

三、总结

这道题还有更秀的一行解题法：

1
2
3
4
5

csharp复制代码public class Solution {
    public double MyPow(double x, int n) {
        return Math.Pow(x,n);
    }
}

是不是秀的头皮发麻。。。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有