快乐的猪头 » 日志 » 如何高效的完成ip地址到实际地理位置的转换
如何高效的完成ip地址到实际地理位置的转换
flyzhang 发表于 2008-06-04 13:03:12
经常上互联网的人都知道，ip是可以很容易的转换为比较精确的地理位置的（比如以前的QQ IP版），你所需要的只是一个ip段到地理位置的库文件（比如说纯真IP库）。但是当你需要将以亿作为单位的ip记录转换为地理位置的时候，问题就来了：
使用MySQL数据库将是一个非常缓慢的过程（至少当时我在使用MySQL 4的时候，对此无可奈何）。后来选择的方式是抛弃数据库，直接使用自己手写的程序进行处理，基本的设计是这样的：
经过这样改造，上亿的数据ip转换也就是分分钟的事情。
目前想到的两个改进是：
使用MySQL数据库将是一个非常缓慢的过程（至少当时我在使用MySQL 4的时候，对此无可奈何）。后来选择的方式是抛弃数据库，直接使用自己手写的程序进行处理，基本的设计是这样的：
- 设计一个ip段类（low ip， high ip），如果low ip 等于 high ip意思就是这个ip段已经退化为一个ip地址了
- 重载ip段类的==,<,>运算符，如果ip段互相包含就是相等，ip段互不相交就是<或者>，由于本应用不会出现ip段交叠而不重合的情况，所以上面的定义就已经足够了
- 使用STL的Map容器，把ip段类和地理位置装入，由于Map容器是才用红黑树实现的，红黑树是一种比较好的平衡检索树，将使得后面的查找过程相当快速，而且你在构造这个检索树的时候也会很放心和简单（至少比自己去写一个平衡树简单多了，而如果简单使用二叉查找树的话，处理树的平衡是个问题）
经过这样改造，上亿的数据ip转换也就是分分钟的事情。
目前想到的两个改进是：
- 在查找前，加入一个cache层，因为据统计ip记录中每个ip平均重复出现的次数>6，这样的话至少有20%~40%的树查找操作可以在cache里面常数时间完成
- 使用hadoop，让这个程序成为分布式的
相关日志:
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
