State changes are, relatively speaking, an expensive operation and texture and shader state changes in particular can have the largest overhead. So yes, if you structure your render loop in such a way as to constantly change the shader and textures bound to the pipeline, that will have a negative impact on render performance. That impact may not be noticeable depending on the overall number of binds, however, it's still good to be aware of it.
Your second example will result in fewer state changes than your second example, and it is generally the way you want to go, especially for solid objects: essentially, sort what your going to render by shader and texture so that you can bind the appropriate combination and then render several objects using those resources. Transparent objects also need additional depth-based sorting or require you to use an order-independent transparency technique such as depth peeling.
An octree can be a useful optimization but it is intended as a means to cull out entire objects that are not visible or otherwise contributing to the scene. You should only have one octree, maintaining an octree-per-material is wasteful and doesn't provide you any real benefits.