索引一般比较大，所以大部分情况下索引是存在磁盘的索引文件上，也有可能是存在数据文件上。
索引的种类有很多：主键索引（这是最常见的一种索引，主键不能为空且必须唯一）、唯一索引（相对于主键索引，它的值可以为空）、全文索引（在char、varchar、text类型可以使用）、普通索引、前缀索引。按照列数来区分：单一索引、组合索引（多字段组成）
2.MYSQL索引的数据结构
在讲解MYSQL索引的数据结构之前，我们先看看了解一下其他的数据结构，看看他们的优缺点进行对比。
2.1 二叉树
二叉树简单来说就是左节点大于右节点，在理想的情况下，他的查找速度就接近与二分法的性能O(log2n)。因为在内存排序的时间是非常快的，可以忽略不计，所以总的消耗时间就取决于IO的 *** 作次数。二叉树查找速度取决树高,每次查询接口都是一次IO *** 作，也是性能的瓶颈所在。
但是也会有这种一种情况,同样也是二叉树，但是他的树非常高，导致查询一次需要多次IO *** 作，效率及其低下
2.2 平衡二叉树
平衡二叉树可以解决二叉树不稳定导致查询效率低下的缺点。平衡二叉树的特点：树的左右节点层级最高相差一层。在插入或者删除的情况下，通过左旋转或右旋转使得整个二叉树平衡，不会出现层级相差很多的情况。平衡二叉树的性能接近二分法查找O(log2n)。
平衡二叉树查找id为8的记录，只需要IO *** 作2次即可。但是仔细想一下，如果数据量很多呢？假设数据表有100W的数据，根据O(log2n)计算，大约需要20次IO *** 作。磁盘寻道大概需要10ms，总的查询时间为20 * 10 = 0.2，效率也比较低下。
还有就是平衡二叉树不支持范围查询，范围查询每次都需要从根节点遍历，效率及其低下。
2.3 B-树(改造二叉树成多叉树)
之前的几种树形结构适合与小数据量的内存查找，也叫做内查找。在1970年，R.Bayer和E.Mccreight提出了一种适合于外查找的平衡多叉树B-树。MYSQL数据文件是存在磁盘的，每次都是按照一页大小（一般而16K）读取内存。像二叉树、平衡二叉树，每次读取节点都要进行一次IO *** 作，所以树越高IO *** 作次数越多。想要提高
Hi，这是一个很有意思的问题，二叉树，无限极分类一般都会用到递归。这里使用函数来模拟mysql查询，解决思路如下：
<?phpheader("Content-type:text/htmlcharset=utf-8")
$data = array(
array('id'=>1, 'pid'=> 0, 'name'=> 'name1'),
array('id'=>2, 'pid'=> 1, 'name'=> 'name2'),
array('id'=>3, 'pid'=> 2, 'name'=> 'name3'),
array('id'=>4, 'pid'=> 3, 'name'=> 'name4'),
array('id'=>5, 'pid'=> 2, 'name'=> 'name5'),
array('id'=>6, 'pid'=> 2, 'name'=> 'name6'),
array('id'=>7, 'pid'=> 2, 'name'=> 'name7'),
array('id'=>8, 'pid'=> 7, 'name'=> 'name8'),
array('id'=>9, 'pid'=> 8, 'name'=> 'name9'),
array('id'=>10, 'pid'=> 9, 'name'=> 'name10'),
array('id'=>11, 'pid'=> 10, 'name'=> 'name11'),
array('id'=>12, 'pid'=> 11, 'name'=> 'name12'),
array('id'=>13, 'pid'=> 12, 'name'=> 'name13'),
array('id'=>14, 'pid'=> 13, 'name'=> 'name14'),
array('id'=>15, 'pid'=> 14, 'name'=> 'name15'),
array('id'=>16, 'pid'=> 1, 'name'=> 'name16'),
array('id'=>17, 'pid'=> 16, 'name'=> 'name17'),
array('id'=>18, 'pid'=> 17, 'name'=> 'name18'),
array('id'=>19, 'pid'=> 18, 'name'=> 'name19'),
array('id'=>20, 'pid'=> 3, 'name'=> 'name20'),
array('id'=>21, 'pid'=> 3, 'name'=> 'name21'),
array('id'=>22, 'pid'=> 2, 'name'=> 'name22'),
)
$result = array()
$id = 2
$lv = 20
get_child_node_nums($id, $lv, $result)
foreach($result as $no => $row)
{
echo '第'.($lv-$no+1).'层有'.count($row).'个叶子节点'.'<br/>'
}
p($result)
//模拟mysql根据pid获取多行记录
function fetch_rows($pid=0)
{
global $data
$pid = (int)$pid
$items = array()
//相当于sql语句:select * from test where pid=$pid
echo "select * from test where pid=$pid<br/>"
foreach($data as $row)
{
if($row['pid'] == $pid)
{
$items[] = $row
}
}
return $items
}
//$id为父节点id, $lv为深度, $result为引用传值结果数组
function get_child_node_nums($id, $lv, &$result)
{
//首先根据其id作为子节点的pid获取其所有子节点
$children = fetch_rows($id)
if($children)
{
//存储其叶子节点
if(isset($result[$lv]))
{
$result[$lv] = array_merge($result[$lv], $children)
}else{
$result[$lv] = $children
}
$lv--
if($lv > 0)
{
foreach($children as $child)
{
$id = $child['id']
get_child_node_nums($id, $lv, $result)
}
}
}
}
function p($var)
{
echo '<pre>'
if($var === false)
{
echo 'false'
}else if($var === null){
print_r("null")
}else if($var === ''){
print_r("''")
}else{
print_r($var)
}
echo '</pre>'
}
输出结果如下：
select * from test where pid=2select * from test where pid=3
select * from test where pid=4
select * from test where pid=20
select * from test where pid=21
select * from test where pid=5
select * from test where pid=6
select * from test where pid=7
select * from test where pid=8
select * from test where pid=9
select * from test where pid=10
select * from test where pid=11
select * from test where pid=12
select * from test where pid=13
select * from test where pid=14
select * from test where pid=15
select * from test where pid=22
第1层有5个叶子节点
第2层有4个叶子节点
第3层有1个叶子节点
第4层有1个叶子节点
第5层有1个叶子节点
第6层有1个叶子节点
第7层有1个叶子节点
第8层有1个叶子节点
第9层有1个叶子节点
Array
(
[20] => Array
(
[0] => Array
(
[id] => 3
[pid] => 2
[name] => name3
)
[1] => Array
(
[id] => 5
[pid] => 2
[name] => name5
)
[2] => Array
(
[id] => 6
[pid] => 2
[name] => name6
)
[3] => Array
(
[id] => 7
[pid] => 2
[name] => name7
)
[4] => Array
(
[id] => 22
[pid] => 2
[name] => name22
)
)
[19] => Array
(
[0] => Array
(
[id] => 4
[pid] => 3
[name] => name4
)
[1] => Array
(
[id] => 20
[pid] => 3
[name] => name20
)
[2] => Array
(
[id] => 21
[pid] => 3
[name] => name21
)
[3] => Array
(
[id] => 8
[pid] => 7
[name] => name8
)
)
[18] => Array
(
[0] => Array
(
[id] => 9
[pid] => 8
[name] => name9
)
)
[17] => Array
(
[0] => Array
(
[id] => 10
[pid] => 9
[name] => name10
)
)
[16] => Array
(
[0] => Array
(
[id] => 11
[pid] => 10
[name] => name11
)
)
[15] => Array
(
[0] => Array
(
[id] => 12
[pid] => 11
[name] => name12
)
)
[14] => Array
(
[0] => Array
(
[id] => 13
[pid] => 12
[name] => name13
)
)
[13] => Array
(
[0] => Array
(
[id] => 14
[pid] => 13
[name] => name14
)
)
[12] => Array
(
[0] => Array
(
[id] => 15
[pid] => 14
[name] => name15
)
)
)
亲测，望采纳^_^。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）