mysql位运算效率_使⽤MySQL的位运算实现⾼效的权限管理
⼩技巧
作者：刘杰
【背景介绍】
这是⼀个在⼥装项⽬中碰到的实际问题，⽹站的权限管理与省份相关，权限管理涉及两种⾓⾊：⽹站运维⼈员，商家。⽹站的运维⼈员可以管理不同省份的商家，商家具有在不同省份进⾏销售的权限，即两种⾓⾊与省份均是1对多的关系。
举个例⼦，某运维账号A具有浙江，上海两处站点管理权限，商家账号B具有浙江销售权限，商家账号C具有上海销售权限，商家D具有江苏和浙江的权限。那么运维账号A只能管理BC，不能管理账号D，因为D具有A所不具有的江苏权限。个人网站设计规划书
图1 权限对应关系图，A管理BC，⽆法管理D
那么问题来了，对于某个登录的运维账号，如何在⼤量商家账号中快速出⾪属于该运维账号的呢?spring cloud feign调用原理
【抽象模型】
设运维账号具有的权限的省份集合是O，例如O={浙江，上海}，可以管理的商家账号集合为M。设商家账号集合为B，其中每个元素是商家销售站点的集合。例如B={B1,B2,B3,B4}，B1={浙江}，B2={上海}，B3={浙江，上海},B4={浙江，江苏}，那么计算该运维账号能够管理的商家账号的集合，即Bi∈B，如果Bi ⊆O，则Bi∈M。
图2 判断⼀个集合是否为另⼀个集合的⼦集
【普通解决⽅案】
从抽象模型来看，如果我们设计⼀张表存储商家和销售省份的对应关系，直观的想法是，对于给定的运维账号，遍历所有的商家账号
(O(n))，然后对于每个商家账号计算其对应省份集合是否为运维账号省份集合的⼦集，判断集合A是否为集合B的⼦集的时间复杂度根据算法不同分别为:
根据⼦集的定义判断时间复杂度为O(n^2)
算法优化为先排序后后遍历的⽅法时间复杂度为O(nlgn)
因此整体的时间复杂度是O(n^2lgn)
【⾼效解决⽅案】
普通的解决⽅案，时间复杂度很⼤，且设计⼀张关系表存储商家和省份的对应关系占⽤较多空间，因此在时间和空间上都可以进⼀步提升。在减少存储空间上，我们容易联想上使⽤BitMap存储账号对应的省份关系，例如，假设⼀共有浙江，江苏，上海三个省份，则可以使⽤三位bit表⽰账号与省份对应权限，三位bit从⾼到低依次表⽰浙江，江苏，上海，那么：
001表⽰具有上海权限
011表⽰具有江苏和上海权限 110表⽰具有浙江和上海的权限关于css以下说法错误的是
service的用法及短语
上⾯的例⼦中，O={浙江，上海}，则bitVal(O)=110,B={B1,B2,B3,B4}，则bitVal(B)={100,001,101,011}。依次类推可以采⽤34位bit 存储账号具有的省份权限。
在提升时间复杂度⽅⾯，可以采⽤位的与操作提⾼算法效率，因为如果集合A是集合B的⼦集，则满⾜
bitVal(A)&bitVal(B)=bitVal(B)，bitVal表⽰对应的bitMap值。例如：
bitVal(O)&bitVal(B1)=110&100=100=bitVal(B1)，则B1∈M bitVal(O)&bitVal(B4)=110&011=010!=BitVal(B4)，则B4∉M
通过位与操作，可以通过⼀次操作判断出⼆者是否具有包含关系，时间复杂度为O(n)，我们可以将权限的bitmap的值设为数据库的⼀个字段，则判断是否为⼦集的操作都可以在数据库端完成。杭研所使⽤的分布式DDB最新版本已经⽀持了位操作，因此这个针对某个运维账号选择它可以管理的商家账号完全可以通过⼀个sql语句完成。
在实践中另⼀个提交效率的⽅法是在⼆进制与省份转换的中，直观的想法是遍历⼆进制的每⼀位，取出其为1的所有位得到其所表达的省份的集合，这个算法与⼀个⾯试题类似：计算⼀个⼆进制数的1的个数，代码如下：
int count=0;
while (fmt != 0) {
long fmtleft = fmt & (fmt - 1);
count++;
fmt = fmtleft;
}
这个算法的⼀个改进之处是“略过”为所有为0的⼆进制数字。代码如下：
public static List getCodeListByProvinceFmt(long fmt){
List retList = new ArrayList<>();
while (fmt != 0) {
//通过减法略去所有为0的位
long fmtleft = fmt & (fmt - 1);
/
/计算此时最⾼位为1的数值，并转换成对应省份codemysql面试题sql
long singleFmt = fmt - fmtleft;
Long code = (singleFmt);
retList.add(code);flowplayer下载官方
fmt = fmtleft;
}
return retList;
}
该算法的时间复杂度为bitMap中1的位数，最坏情况下为O(n)，最好情况下为O(1)，在⼀个账号对应较少省份情况下，效率可以很好。
【结语】
使⽤BitMap结构存储账号对应省份数据字段，既可以减少存储空间，也提交了判断是否为⼦集的效率。
本⽂来⾃⽹易实践者社区，经作者刘杰授权发布

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。